O fato de a mensagem ser tratada como SPAM pelo hotmail não está diretamente relacionada com a mensagem em si.
Alguns detalhes fazem diferença.
Se o email provier de um ip que não é entrada MX do dominio, geralmente ele fica marcado como SPAM.
Tente usar headers completos e nunca use um email em FROM com um dominio diferente do que o dominio do ip.
No mais é marcar o remetente como seguro que não irá mais cair na caisa de lixo eletrônico.

Entendi, então uso estes headers aqui

$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/html; charset=iso-8859-1\r\n";
$headers.="From: contato@dominio.com.br \n";


Você acha que falta mais algum ?

Abraço e obrigado pela resposta

Alexandre, o header pode conter várias outras informações. Alguns exemplos são:

Message-Id - Identificador único da mensagem
From - Nome/E-mail Remetente
To - Nome/E-mail Destinatários
Cc - Nome/E-mail Destinatários por cópia
Bcc - Nome/E-mail Destinatários por cópia oculta
Reply-To - Nome/E-mail para quem responder
Subject - Assunto
Date - Data no formato date('D, d M Y H:i:s O')
User-Agent - Programa usado para enviar o e-mail
MIME-Version - versão dos formatos mime
Content-Type - formato mime do conteúdo do e-mail
X-Mailer - programa usado para enviar o e-mail
Disposition-Notification-To - Nome/E-mail de quem deve ser notificado da chegada do e-mail
X-Priority - número da prioridade e o nome, que pode ser:
1 (Highest)
2 (High)
3 (Normal)
4 (Low)
5 (Lowest)

Eu recomendo utilizar a classe PHPMailer, ela adiciona esses cabeçalhos. Sem falar que envia por SMTP, por uma conta do Google e etc. Baixe o código e la dentro vai ter uma pasta de exemplos.

http://phpmailer.worxware.com/