On your computer:
Most Internet Cafes, and many ISP's have the default email sending (SMTP) port 25 blocked. We run a second mail server on port 587 in order to get around this problem.
If you are using your 4yourwebsite-hosted server to SEND emails then you will need to make a change to your settings. In your email client (Outlook, Thunderbird, Pegasus, etc.) go to your outgoing mail server settings and change the port from the default port 25 to port 587.
On your mobile phone:
Cell Phones with Outlook will have a place for you to enter Domain under the incoming and outgoing servers. If your phone is receiving email OK, but gets an error when sending, then your problem (most likely) is that you have filled in the Domain field -- remove contents of the Domain field (leave it blank) and that should resolve your problem.