mmm....
no necesitas mas ayuda, ya te dieron la información necesaria...
1.- Si tu nuevo proveedor no tiene habilitada la función mail() pues no hay mas que hacer... no crees??
2.- Si no hay tal función mail, aun puedes usar un SMTP para enviar tu email... usando PHPMailer, etc, etc...
3.- Si necesitas saber sobre alguna clase de terceros para el envío de email, pues.... investiga en el foro... ya se ha hablado bastante, o en Google... no seas
suerte!