Ciao,
ti consiglio di utilizzare la classe PhpMailer per semplificarti a massimo la vita, trovi a questo link una brevissima guida scritta da me con tuto quello che ti serve.

Per quanto riguarda il server SMTP ti consiglio di usare un account free di libero, tra i test che ho fatto è quello che da meno problemi, le mail le invia il 90% delle volte, con gmail non sono riuscito nemmeno io.

Saluti