Si tienes algún tipo de proxy, firewall o incluso antivirus que te scanee el puerto por defecto del SMTP (25) .. es lógico que te dé esos problemas (de conflictos).
Si ves que en otro puerto te funciona .. sólo debes indicarlo a PHP que cambiastes de puerto .. Por defecto lo hace en el 25 para el SMTP si deseas otro debes decirselo en tu php.ini:
SMTP=localhost (o IP del servidor que corra ese servidor SMTP)
PORT = 23
El tema del parámetro "PORT" no está disponible para toda versión de PHP . .creo que apareció sobre PHP 4.3.?... revisen la documentación oficial de PHP para confirmarlo:
www.php.net/mail
Si su versión de PHP no les permite seleccionar el puerto para el servidor SMTP y así usar "transparente" la función mail() de PHP original, pueden usar otras alternativas para la función mail() (esto no sustiyue o excluye la necesidad de tener instalado un servidor SMTP en su servidor o bien apuntar a otro externo):
PHP Mailer
http://phpmailer.sourceforge.net
Esa classe (OOP, objeto) de PHP permite enviar e-mails por servidores SMTP directo, enviar archivos adjuntos de forma cómoda .. etc.
Un saludo,