OK so now we know:
1. Server OS of the domain that worked - Linux
2. Host of the domain that worked
3. Server OS of the domain that didn't work - Linux
4. Host of the domain that didn't work
4. Server settings you are using
PHP hides all of the internal workings from the browser so the links don't help. The domain names don't matter and I don't want to track down the hosting company through IP addresses.
The only thing I can suggest is to compare the two setups and find out what is different between the domains. You can also check with the support forum for the hosting company and see if others have had issues sending out email and what the requirements are.
Since it works on one domain, it is not an issue with the script.
Good luck with it.