I don't want to simplify the matter but, is it possible someone is just spoofing your domain and sending emails with viruses attached? Anyone who has a recieved a legit email from your company will know the path that it takes. After that, they can just spoof all the legit server transactions that take place and make it look like the email is originating from within your domain. At some point there would be some determining factor that shows the email didn't originate from within your domain (possibly an extra mail server transaction of an open SMTP server) It's too bad we don't have the offending email (the one with a virus attached) so we could check out the header info.
This could explain why your network appears clean but keeps getting black listed. Just a thought.