[Resolvido] Problemas com a função mail

Olá! Estou com um problema com a função mail do PHP. Mesmo com o código mais simples possivel, não funciona:

CODE
<?
if(mail("meuemail@gmail.com", "Funcionou!!", "Só alegria XD"))

echo "enviou<br/>";

else

	echo "não foi... ¬¬<br/>";

?>

"meuemail" obviamente é um email válido no gmail e eu sei que o problema não tem a ver com o domínio do email, pois já usei este mesmo email para testes e funcionava, só que o site ficava em outro servidor.

Bem, quanto ao meu problema, a função mail está retornando true, mas eu NUNCA recebo o email. Só posso imaginar que o problema esteja no servidor onde o site está hospedado, mas não entendo lhufas de configuração de servidor ou do PHP.

Será que alguém pode me dar uma luz sobre o que está acontecendo?