Hai fatto caso se quelle che arrivano nello spam o non arrivano sono indirizzate a determinati domini? Tipo hotmail, libero... sono i più problematici per via delle regole dei loro filtri.
Ricordati sempre gli header: mail from, reply to ecc... fa una ricerca qui sul forum, se ne è parlato un bel po' di volte.

Contatta anche il tuo hosting per segnalare il problema, potrebbe esserci il record DKIM da impostare/modificare sul server.