Quel est ton hébergeur ? certaines hébergeurs comme NexenServices ont modifié la fonction mail()... peut etre que le probleme vient de là, même si la réponse de ton hébergeur semble prouver le contraire...
sinon le problème peut peut etre venir du fait que les headers ne sont pas définis, certains clients mails sont plus exigeants...
essaye ça :
if(mail("newbiel_AT_yahoo.fr","send message","its working"," From: webmaster_AT_yoursite.com")) // (remplacer _AT_ par l'arobase...) echo "message sent!"; else echo "Error !!!";
et autre chose as tu bien remplacer le AT par @ ??