ah ecco...

probabilmente è un hoster un po troppo "aperto" ed è stato inserito in una black list

cmq si devi mettere qualcosa tipo
Message-ID: <20051014113717.13971.qmail@miohoster.ru>

però per semplificarti la vità basterà mettere prima della chioccola un md5(uniqid(microtime(), true)) e dopo la chiocciola il tuo dominio di secondo livello ovvero dominio.tld e non www.dominio.tld