I had the same problem. It started during the second week of july. what i did :
1) The spammer sends out mail as an authenticated user i came across these usernames
admin
root
webmaster
www
data
server
test
So i created these usernames and put a strong password and when the spammer was trying to authenticate failed.
This stopped the relayig problem but i still have a lot of failed authentication attempts.
2) I used easy to guess or to remember passwords because the users of my network are people who dont know much about computers and long funny passwords confused them. I changed that. Now we use only strong passwords. There are several programs that might help you generate good passwords.
3) i disabled the guest account. I DIDNT delete it.
4) I deleted accounts that previous administrators had left in the server.Actually there is no reason for more than 2 admin accounts.the ordinary and a backup. I found about 5 or 6 in the server.
5) READ these links they are VERY important. As you ll see there is a flaw in the SMTP service in Exchange 5.5 either on winnt4.0 or win 2000, that allows someone outside your company to authenticate as a user of your company and send out mail. The fix was released AFTER Sp4 for exchange 5.5 so even if you have sp4 installed youre still affected by the flaw.
Microsoft says that if you install the fix you re ok. But i m sure that it was a combination of all these steps that stopped the spam from passing through my server.
I STILL have many failed authentication attempts but it looks like everything is working fine now.I even deleted the accounts that i created to stop the spammer from authenticating and although he is trying to connect he fails.
SMTP service is working fine.If you want to stop even the connection attempts my best bet is to ban the ips on a firewall or a router .I tried with the firewall and it worked. But i dont wanna go through that cause i m afraid i might cut off legitimate mail.
Finally if for some reason you dont want to do anything from what i have described or you just want to increase even more the security on your server you can go to exchange administrator.open the properties for the internet mail service and you ll see a tab called delivery restrictions. It has 2 columns one says accept mesgs from and the other reject mesgs from. Put all your legitimate domain users in the accept mail from list, apply , restart ims and you re done.Even if someone authenticate as a domain user he wont be on your accept mail from list so his mail is automatically rejected.
I hope it works out for you guys as it did for me.
good luck
george