Ser marcado como "spam" é diferente, mas está relacionado. A autenticação de e-mail não influencia a entrega nesse sentido de spam / não-spam, a autenticação de e-mail é apenas uma maneira de mostrar que você é quem você diz ser. Você não está falsificando. É isso aí. É mais uma questão de segurança, pois os phishers e spammers usam frequentemente domínios de outras pessoas para fazer o seu trabalho sujo, por isso, configurar o email auth torna mais difícil para os maus arruinarem o seu nome de domínio. Isso torna o e-mail mais provável de ser aceito pelo servidor de e-mail (não rejeitado), mas não influencia se ele é rotulado como "spam".
As decisões de spam são feitas por uma combinação de reputação de endereço IP / domínio, envolvimento de destinatário com emails (no caso de marketing por e-mail), reclamações de spam e conteúdo (menos importante do que costumava ser). Então eu diria que para investigar isso, você deveria verificar sistematicamente tudo isso com ferramentas on-line. Você verificou tudo isso, incluindo a execução do conteúdo por meio de spam, um verificador de spam apenas por uma boa medida?
BTW, desde que você mencionou o Hotmail, a Microsoft tem algumas dicas para solucionar problemas de entrega de e-mail para outlook.com e outros domínios da Microsoft.