Every mail server setup can function a bit differently...ESPECIALLY with anonymous emails. Do you have Windchill setup to use an email username/password? If not I would do that immediately as it'd probably fix your issue.
If the email server is an Exchange 2007, there is a new security into it (vs 2003) that blocks Java automated process to send emails in the outside world (we all wish some spam guys where using it OOTB...)
In order to get things working there is the following bypass:
Go to the Exchange Management Console> Go to Server Configuration> Select Hub Transport. Create a New Receive Connector. Create a new connector, Make sure the remote IP range you add contains the IP of the Windchill server. Go to the properties of the connector you created and go to the Authentication tab. Select Externally Secured.
You might want to have a different IP from the usual SMTP Server. If so then just modify the SMTP Server properties in site.xconf for Windchill and roll on....