What are the mail scanner settings?
Did you put a checkmark in front of scanning outbound mail?
What email client do you use?
Are you using ssl?

Have you run a online scan for malware?
http://housecall.trendmicro.com
http://www.bitdefender.com/scanner/online/free.html
http://www.eset.com/us/online-scanner/