Bem, depois de inumeros testes não consegui arranjar solução para isto...
Tentei de tudo, experimentei utilizar todas as headers que um email pode utilizar e nada...
Esta situação é das mais dificeis de resolver que encontrei até hoje...
Simplesmente nada parece funcinar e inevitavelmente todos os emails enviados com a função mail(); do php para o hotmail acabam na pasta spam...
Mesmo depois de esgotados todos os meus recursos efectuei uma aprofundada pesquisa no google e a unica coisa que encontrei e que aparentemente soluciona isto é por meio de um pagamento de uma larga dezena de dolars a hotmail para que não considere os mails como spam. Já não me lembro onde li isto, se é verdade, tambem não sei, mas pelo que li tudo indica que sim.
Agora não tou é a ver muita gente a pagar uma quantia exorbitante só para não ver os seus mails a cairem na caixa de spam do hotmail...
Até porque ao que parece, este caso verifica-se apenas no hotmail.
De qualquer maneira, se alguem encontrar uma solução viável sou todo olhos para lê-la.