However your network is built could not matter less, it is your outgoing e-mail that is causing the problem.
It is usually relay issues or a user who sent out a malicious file (most likely accidently).
Have your system/network admin visit:
http://spamcop.net/bl.shtml
and have your company's IP removed from their database, locate the issue and resolve it ASAP or they can keep you blocked for good if the same action is repeated.
Spamcop for those who don't know is a mail-filter that many corporations used.