A mi me pasa exactamente lo mismo: funciona con todas las cuentas menos con las de Gmail. (Mucho me temo que algo en gmail los filtra).
estos son mis headers (a ver si sabéis de alguno que haga de chivato para Gmail):
Código:
// To send HTML mail, the Content-type header must be set
$headers = 'MIME-Version: 1.0' . "\r\n";
$headers .= 'Content-type: text/html; charset=iso-8859-1' . "\r\n";
// Additional headers
$headers .= 'To: '.$the_admin['user'].' <'.$the_admin['email'].'>' . "\r\n";
$headers .= 'From: '.$is_logged['user'].' <'.$is_logged['email'].'>' . "\r\n";
$headers .= 'Reply-To: '.$is_logged['user'].' <'.$is_logged['email'].'>' . "\r\n";