Musiałem, że jest to wina funkcji mail() więc skorzystałem z bardziej zaawansowanego narzędzia jakim jest PEAR mail i wysyłanie maili przez smtp.
Niestety to rozwiązanie znowu spowodowało uznanie wiadomości jako spam. Poszukałem trochę i dowiedziałem się że autroyzację można przeprowadzić za pomocą DKIM lub DomainKeys. Niestety nie mam pojęcia jak tego dokonać. Może byłby ktoś w stanie po kolei opisać co krok po kroku powinienem zrobić by zastosować jakiekolwiek z tych rozwiązań.
Domena z której pochodzi email została zarejestrowana na home.pl (do konta domeny mam bezproblemowy dostęp jak do maila stworzonego specjalnie dla wysyłanych newsletterów).
A kod php z jakiego korzystam wygląda tak (znaleziony w necie tylko wpisałem w nim swoje dane, których oczywiście tu nie podałem

require_once "Mail.php"; $from = "Twoje Imie <mail@nadawcy.pl>"; $to = "Imie Odbiorcy <mail@odbiorcy.pl>"; $subject = "Temat wiadomosci ;)"; $body = "Tresc wiadomosci"; $host = "serwer.smtp.com"; $username = "smtp_username"; $password = "smtp_password"; 'To' => $to, 'Subject' => $subject); 'auth' => true, 'username' => $username, 'password' => $password)); $mail = $smtp->send($to, $headers, $body); if (PEAR::isError($mail)) { } else { }