Lo que puedes hacer es usar PHPmailer pero indicandole tú el servidor smtp que quieres que use o también puedes hacerlo de la forma que viene aquí (abriendo un socket):
http://www.programacion.com/php/articulo/fli_phpsmtp/
En cuanto a servidores de correo y yo tengo el de argosoft y la verdad es que siempre me ha funcionado y es muy sencillo de configurar
