Envio de emails por PHP

Senhores, boa tarde.

Estou usando a função mail() do PHP conforme visto em milhares de tutoriais espalhados na internet. A questão é a seguinte:

Tenho um servidor de email interno da empresa... até ai tudo bem! Envio um email interno da empresa(@dominiodaempresa.com.br) e maravilha... o email chega conforme esperado! Porém, se eu envio para um email externo(@gmail.com ou @hotmail.com, ou @qualquerdominio.com.br) o email não chega! E não dá maiores explicações ou mensagens de erro.

Alguém pode me ajudar?

Obrgiado!