Do you have an e-mail antivirus program that is checking your e-mail? If so, check to ensure that the port it is...
passing the mail through to the Exchange server is secure.
Often these e-mail programs will accept mail through port 25, and then check it and pass it through port 1025. The antivirus program may not allow spam relays, but you need to double-check the other port to ensure that it too is secured properly.