Bueno, con el "SMTP" servidor .. no tendrán problemas .. pero parece ser que no configuraron PHP para usar su sendmail o el MTA que usen ...
En tal caso podrías verificar ese punto con tu proveedor. Y . si quieres probar por tu cuenta .. puedes usar alguna classe de PHP que te permita enviar e-mails sin usar mail() de PHP y haciendolo directamente al servidor SMTP que usen ..
Ejemplo:
PHP mailer
http://phpmailer.sourceforge.net
Ahí puedes usar el SMTP .. apuntando a "localhost" o a la IP que ejecuten ese servidor. También puedes usar sendmail (desde esta classe) .. La ruta a tu sendmail (si lo usan) te lo deben de proporcionar los Srs. de tu servicio de hosting (lo suelen dar junto con la documentación para Perl ...)
Un saludo,