Question:

Spam / Malware is on a pc / server in our office.  We have scanned and cleaned our PC’s repeatedly, with Anti-Virus, but we still get shutdown by our smarthost because of spam/high activity.  My question is this, what tool do they use to find that information out?  Does it run in windows?  What is the difference between SPAM and MALWARE?  To many questions…i know.  But its killing me how this happens….Its frankly, embarrassing….

Solution:

http://www.amset.info/exchange/spam-cleanup.asp

Note Simon the author of this websites comments toward the bottom of the above links webpage under the heading
Check whether you are under an NDR Attack
By the sound of things you need to spend some quality time on your own reading the above links comments and systematically going through all the suggestions, unfortunately there is no quick fix this needs doing correctly.
Once you have cleaned up the exchange and made sure its not an open relay you should also see a marked differance in the speed of incomming and outgoing emails.

http://www.amset.info/exchange/message-tracking.asp

To track your messages

http://www.amset.info/exchange/imf.asp

To at the very least to get some kind of anti spam prevention in place. Your spoilt for choice here to be honest, We use messagelabs for filtering our email.
Your current ISP/Hosting company may provide some solutions as well.
Obviously these are for incoming