Well, i had the same problem with mass email and contact email also, two weeks involved searching the solution and nothing. My email is from a telephone company and used for many years.
The final solution to this issued was change the webmaster email and also my email to gmail account and all going well.
At this time with many test all is full working.
My local config as follow
# Email Settings
Config::Set('EMAIL_FROM_NAME', '');
Config::Set('EMAIL_FROM_ADDRESS', '');
Config::Set('EMAIL_USE_SMTP', false);
# Add multiple SMTP servers by separating them with ;
Config::Set('EMAIL_SMTP_SERVERS', '');
Config::Set('EMAIL_SMTP_PORT', '25');
Config::Set('EMAIL_SMTP_USE_AUTH', true);
Config::Set('EMAIL_SMTP_SECURE', 'ssl'); # must be "ssl" for Google Apps
Config::Set('EMAIL_SMTP_USER', '');
Config::Set('EMAIL_SMTP_PASS', '');
App config with no changes.
Regards
Luis