The way that "relay" can present itself can be very interesting. The customer reported that he was an "open relay" and followed http://support.microsoft.com/default.aspx?scid=kb;EN-US;324958 to "clean it up". After about a month, the problem came back. Interesting...
Using http://support.microsoft.com/default.aspx?scid=kb;EN-US;324958, a quick test determined he was not an open relay in the traditional sense of the term. The customer was using the Pop3 Connector to retrieve email. Another symptom was that the Pop3 Connector was not delivering email to the users. It would download it from the ISP but the mail would get stuck in C:\Program Files\Microsoft Windows Small Business Server\Networking\POP3\Incoming Mail. There were also about 1,300 emails in C:\Program Files\Microsoft Windows Small Business Server\Networking\POP3\Failed Mail. We opened one of the EML files in notepad and noticed the "TO:" contained about 500 recipients, one of which was for the local domain.
This was a clear indicator that the customer needed http://support.microsoft.com/?kbid=835734.
So...this was a great opportunity for the consultant to sell the customer on a managed solution because this problem SHOULD HAVE NEVER HAPPENED if the server was updated regularly. This fix was offered by Microsoft Update and is also included in SBS2003 Service Pack 1.