¿Quien no ha sufrido los problemas de enviar correos desde su aplicacion web?
A la hora de conseguir esa funcionalidad PHP nos provee de una unica funcion
y si se usa sin mas puede llevar a la frustracion por muchas causas:
* Colega... ¿donde esta mi FROM?
* ¿Por que me cambia el FROM por un www-data@localhost?
* ¿Por que no llega el correo?

En resumen, el problema que tiene esa función es que si se usa sin mas puede que funcione o puede que no dependiendo del entorno: windows, linux, marca de servidor de correo, configuracion especifica local y del servidor destinatario, etc...
Pues bien, pese a que PHP provee y sigue manteniendo esta funcion tan simple y que en apariencia no hace lo que promete FUNCIONA. La clave esta en que Hay que establecer correctamente las cabeceras.
¿Cómo se hace eso? ¿Dónde busco?
No hay que complicarse, en el caso de PHP su sitio oficial dispone de la documentacion de funciones con muuuuchas aportacion de programadores. Este ejemplo que nos dan funciona muy bien: 
<?php
$to      = 'pello@kgb.ru';
$subject = 'Hola';
$message = 'Esto llega por mis cojones';
$headers = 'From: webmaster@example.com' . "
" .
   'Reply-To: webmaster@example.com' . "
" .
   'X-Mailer: PHP/' . phpversion();

mail($to, $subject, $message, $headers);

echo "OK, correo enviado";
?>

A través de la documentacion de la funcion mail podremos contemplar mas casos como el envio de adjuntos, envio en formato HTML, etc... echa un ojo
¿Puedo enviar un correo sin tener levantado un servidor local smtp?
Aunque puede depender de cada entorno, se puede hacer. Por ejemplo, con postfix instalado tenemos un alias del comando sendmail y lo podemos especificar en php.ini. Y es mas, podemos configurar postfix para que le pase el marron a otro servidor SMTP: En /etc/postfix/master.cf a la linea de smtp le metemos una opcion: 
# ==========================================================================
# service type  private unpriv  chroot  wakeup  maxproc command + args
#               (yes)   (yes)   (yes)   (never) (100)
# ==========================================================================
smtp      inet  n       -       -       -       -       smtpd
        -o smtpd_proxy_filter=192.168.1.2:25