Error while sending mail


I'm getting following error message when I'm trying to add a new user to site and trying to send mails to him.
The Site is Intranet site as well exposed on internet via alternate URL mapping while adding users of local exchange group it does not give any errors but suppose that I add a user having gmail id expressed in his AD that throws following error:

The user or users have been added successfully, but there was an error in sending the e-mail message. The server may not be set up correctly to send e-mail. To verify that e-mail is configured correctly, contact your server administrator.

Best Solution

First verify that the user you just added has a valid email address in SharePoint - don't assume it was picked up correctly from A.D. (Site Setings > People and Groups)

Find out what you have set as the outgoing SMTP server (Central Administration > Operations > Outgoing Email Settings)

Install a tool like the SMTP Test tool on your server (or use Telnet to test manually) and use the same settings/email address. This will tell you if the problem is with SharePoint or your email infrastructure.