email - PHP mail() function will not send to gmail but will send to my non-gmail account

Question

For some reason the php mail() function is not working properly on a site I am building. I tried to troubleshoot the issue down to its simplest form, and came up with this file:

<?php
mail('[email protected]', 'the subject', 'the message', 'From: [email protected]', '[email protected]');
?>

when myEmail is a Gmail account, I never receive the message. However when I use a non-gmail account, I do receive the message. I am at a loss and have tried everything to figure this out. I am starting to think it is an obscure host/server issue. You can see the server specs here: http://aopmfg.com/php.php

Any ideas?

EDIT - let me also add that this was all working fine a few weeks ago, the last time I tested it. No significant code changes since then at all.

EDIT 2 - After reading a similar post I tried adding From and Reply-To headers... still no luck. New code:

<?
$headers = 'From: <[email protected]>' . "
" .
'Reply-To: <[email protected]>';

mail('<[email protected]>', 'the subject', 'the message', $headers,
'[email protected]');
?>

Answer 1

It turns out that Google blocked my server because another site on the same server was hacked and used for spam.

To test and ensure that it was a problem with the server, I created a simple PHP file that would send an email to my email address on page refresh. It worked when I sent to my exchange-based email address, but not to any Google-related accounts.

Code:

$headers = 'From: <[email protected]>' . "
" .
'Reply-To: <[email protected]>';

mail('<[email protected]>', 'the subject', 'the message', $headers,
  '[email protected]');
?>

Thanks for the help all.