Bueno veamos,

FreeSMTP (el link que te di antes) NO Funciona.
O al menos ami no ha parado de tirarme "Recipient Not Valid" por cualquier cosa que haga.

Sugiero que lo desinstales.

Lo que funciona

1.- 1st SMTP Server.
  Aunque sea un programa de pago (tiene un trial de 30 dias), si me ha funcionado y bien.
  Que hacer:
     1. Descargar e Instalar 1s SMTP Server (http://www.emailarms.com/products/1st_smtp.htm)
     2. Ejecutar 1st SMTP Server.
     3. Ejecutar el archivo PHP con la funcion mail.
     3.1. En mi caso este:
     

<?php
$para = 'correo@destinario.com'; // El correo que va a recibir el mensaje
$titulo = 'Probando SMTP'; // Titulo del mensaje
$mensaje = 'Hola mundo!!!'; // Mensaje
$headers = 'From: micorreo@midominio.com '; // correo desde el que supuestamente ha sido enviado.
mail($para, $titulo, $mensaje, $headers);
?>

    4. Comprobar el correo destinatario, incluida la carpeta spam (El mio acabo aquí xD).


Saludos

Ok, lo miraré.
Muchas gracias