We use database mail extensivly to report server information back to a monitoring environment. Typical issues we see are things like the mail server name is wrong or the SQL Service account can't use the mail server, or the mail server hasn't been configured to forward e-mail from the SQL Server.

The issue is almost always on the mail server side, and I recommend you get the mail server log checked for errors related to incomming mail from your SQL server.

Cheers

Leo