If you are on the receiving end of a bot-net that insists on trying to relay spam through your mail gateway, your systems can get into trouble even though relaying is blocked.  A reader wrote in earlier today with his mail gateway under full load only from rejecting the relay attempts. Source IP addrs kept changing, and only by continuously adapting his firewall filters was he able to bring the load down to about one spam relay attempt per second still reaching the email gateway. 

If you are idly bored at the moment, it might be a good time to read up on your firewall's layer-7 filtering capability for SMTP. Chances are there's features in your firewall that can help to off-load relay attacks from the mail system onto the firewall. Of course, if you end up with a D.o.S on the latter, that doesn't accomplish much, either :-)

Update 21:17UTC:  A number of comments indicate that BSD "spamd" seems to be a popular measure used to thwart such relay floods. This sample chapter of "Building Firewalls with OpenBSD" describes how it can be done. Another good description can be found on http://www.openbsd.org/papers/bsdcan05-spamd/  (Thanks, Navan!)
Folks using Postfix might want to take a look at Postgrey, a grey-listing implementation that is apparently also quite effective in squelching crud.