PHP - Enviar email

Hola, hemos cambiado la web de la empresa de servidor. El caso es que la web tiene un formulario que debe ser enviado por email (en PHP). Desde el nuevo servidor no se está enviando. El proveedor nos comenta que el servicio de correo está activado. Creo que el servidor de correo activado es el nuestro propio mail.nombreempresa.com. El tema es que nosotros tenemos nuestro propio Exchange y por eso no queriamos gestionar cuentas de correo desde el dominio de la web que, dicho sea de paso se llama igual que la red interna.

En fin, al cambiar de servidor la web no nos envia el correo. ¿Pueden ser permisos de red?.

Saludos.