On a normally configured Exchange 2003 server, anonymous users can connect to the server only to deliver mail destined for internal users (which are defined by the recipient policy). If an unauthenticated user tries to send spam to an address that isn't in the local recipient policy list, the smtp connection is dropped.
If users are able to connect to your system, and, without authenticating, send email through your server to other external recipients, your system is misconfigured. Either that or one of your user accounts is compromised and an authenticated user is generating all the spam.
But since an external test said that you have an open relay, then you must be allowing unauthenticated users to relay.
Here's one more thing to check: go down into your Connectors, not under Servers -> Protocols. Look at the main SMTP connector there, and check the Address Space tab. It should have a * in the big field. Now look at the bottom. There is a checkbox that says "Allow messages to be relayed to these domains." Make sure that it is NOT checked.
ShackDaddy