OK..
So here's the deal.
Exchange 2003+ is quite the animal, and in a sense, quite the secured beast.
The only way you can use * > Exchange 2003 is to use the FRONT END server. This has SNMP open to * on TCP 25.
There are other ways around it, but this is your best bet.
You can open up relay for everything internal to your IP's, but that's a REALLY bad idea.