Es un problema "comun" en hosting compartido (si alguien en el mismo servidor hace spam te afecta a ti), y en caso de que sea tu propio servidor, seguramente no tienes "Reverse DNS" para la IP (hostname)...
La solucion puede ser facil:
1- Si es tu propio servidor, pide a tu provedor que configure el REVERSE DNS para la IP.
2- Si el hosting es compartido, activa la validacion SPF agregando un registro TXT a la configuracion DNS de tu dominio, eso ayuda a validar que tu correo es legitimo.
3- Si lo anterior no resuelve el problema, da de alta tu dominio en GOOGLE APPS y que GMAIL gestione el correo de tu dominio, para ello debes agregar un registro CNAME y entradas MX (de google) a la configuracion DNS de tu dominio, de ese modo el email apuntara a los servidores de google, si no lo sabes hacer o no tienes acceso, el soporte del hosting te puede ayudar... Despues de eso, en lugar de enviar tus emails via local (funcion mail() de PHP por ejemplo), los envias usando el SMTP de GMail (tendras que cambiar alguna configuracion en el script que hace funcionar tu web para que el correo se envie por SMTP y no usando el servidor de email local), de esa forma SI o SI el correo llegara a la bandeja de entrada.
Saludos, Dasumo.