Envio de correos mediante php

Hola, estoy tratando de utilizar el funcion mail() de php para enviar correo, pero creo que deberia instalar un servidor smtp, he intalado unos cuantos pero cual es mi sorpresa que aunque la funcion mail() lo envia, y en la consola de dichos servidores se visualiza, y en algunos hasta parece que los envie, no se recibe nada en la cuenta que los ha de recibir ...
En la conexion de red, he habilitado la opcion de "Envio SMTP" (o algo parecido), el puerto es el que se pone por defecto, el 25, pero nada. Estoy tratando de enviar a gmail, lo digo por si puede ser un problema.
¿Puedes ayudarme?
Saludos y gracias.

Llegas tarde.
Pero te contaré: la pagina loa tengo alojada en dos sitios, en local y en servidor internet. En local lo he solucionado cambiando el servidor DNS que venia y ahora si que lo envia, pero por ejemplo gmail, lo detecta como spam ...
En el servidor internet no funciona, por lo que le he aplicado una solucion: me bajo las peticiones de suscripcion a mi pagina y desde local envio dichos correos para que se suscriban ...
Las modificaciones aun no están subidas a internet porque estan relacionadas con otras opciones que estoy haciendo para la pagina.
Eso si, si la quieres visitar es: http://imaginis.freei.me, la estoy remodelando o mas bien dicho la veo a remodelar, pero se admiten sugerencias que las puedes dejar en el formulario que hay o enviarme un correo a la dirección que sale alli.
Saludos.