Yo puedo enviar correos mediante mail desde mi servidor local (así que lo que dice el de arriba a parte de estar fuera de tono, no es tan válido). No es un problema usar mail desde el localhost (obviamente par ti si), ya que todos los servidores envían mail desde localhost (si no lo configuras para hacer otra cosa).
Creo que tu servidor SMTP de mail no funciona correctamente. Puedes probar a reinstalar la aplicación, aunque mi experiencia con mail es que siempre va lento. Puedes intentar conectar con un SMTP externo como gmail o hotmail o yahoo... siempre y cuando tengas una cuenta en ellos. Como esos servidores se dedican a eso el envío de correo se hace de forma muy rápida.
Para usar SMTP, puedes usar o la clase MAIL de PEAR (que es un módulo de PHP, quizás lo tengas instalado), o puedes usar una de las múltiples clases de envío de correo vía SMTP que hay. Te mando un link a la mía por si las moscas te interesa:
http://www.anesgysd.byethost7.com/Cl...iler-PHP-.html