Allot of providers have PHP Mail disabled for security.
(block the users to be able to send spam emails or infected emails from php mail function.)
If you have root access, then you can enable it.
You might have to contact your upstream also to make sure all the SMTP ports are open.