Before I've had to deal with other larger companies, client of ours, when we have had e-mail issues with them. Most of the time it's when our messages have been tagged as spam, although right now it's because one of their systems has gone haywire and is repeatedly sending us e-mails. Anyway, my question is how do you get in touch with the email administrator. I've found at some larger companies unless you have the name of the person, the receptionist will refuse to connect you to them (I'd imagine they're acting as the gatekeeper from salespeople asking for "the person responsible for dealing with your printers"). I know we could always try to deal with our contact at the company, but sometimes that can be slow and difficult and these issues are usually time sensitive.
If no one is listed when doing a reverse lookup on the domain name, I'd call them and ask to speak to their information technology department. Introduce yourself as an IT administrator for your company and inform her that you have reason to believe there is a network issue where someone at their company is having issues with your network and you need to speak to the person in charge of their email server. You might get really really lucky and someone might be listed by name on the company's website, too.
I don't know if I'd press that it's not a sales call (they always say that) so much as that you're a network administrator who has found an issue originating with their company that is affecting your network and you need to speak to someone as soon as possible to resolve the issue.
I don't know if I'd hint that you might need human resources or legal to contact them, but you'd really like to get this resolved with their network or system administrator. Depends on how the conversation goes.
I also think that knowing a name doesn't necessarily help. Most sales calls come from someone who knows a name, whether from a mutual contact or a conference or someone dropping a name while they were at a conference or just someone passing the sales call on to you. We get plenty of calls that know a name here and they more often than not insist it's not a sales call, but then proceed to ask questions about our network infrastructure, things we purchase, etc...
Not really an answer..but:
The first thing to do is to make sure that you have covered all your bases. Jeff Atwood wrote a good article about this here. I would at least make sure you have the ptr record and spf entry before I would bug anyone...
Usually emailing email@example.com or firstname.lastname@example.org or whatever contact appears in the other company's DNS records is a good place to start.
I would call the main line and ask for someone in IT security. That usually will get you someone that the receptionist probably won't want to block and is hopefully somewhat technical. Once you explain your issue they should be able to help you get to the email admin.