spamming relay in Exchange server

Our exchange server 5.5 SP 3 has been used by spammers to relay their junk e-mails. How to stop this. The server has routing restriction in place. If I pick “Do not reroute incoming SMTP mail”, I can’t receive e-mail from several my clients. Any suggestions?