Você não deseja apenas verificar o e-mail que sabe enviar, mas procurar por e-mails que não esperava enviar, como scripts comprometidos ou contas de e-mail. E sim, os e-mails de verificação também podem ser marcados como spam. Você pode tentar um double opt-in, onde o primeiro e-mail enviado é pedir permissão para enviar outros e-mails, até mesmo e-mails de recuperação de senha. Então, tenha boas informações de desativação no próprio e-mail.
Dito isto, o seu IP parece estar limpo nas principais listas negras: link
O salto é apenas a Microsoft, e eles simplesmente não jogam bem com o resto de nós. Na minha experiência, nunca encontrei um único incidente de spam sendo enviado por qualquer IP que a Microsoft tenha bloqueado. Suas decisões parecem ser na maior parte arbitrárias, e tipicamente incluirão o bloqueio porque você tem um IP que se parece com um IP que eles bloquearam. Então, solicite um fechamento de lista e não se preocupe muito com isso. Se dependesse de mim, as pessoas parariam de usar esses serviços para o e-mail, mas, desde que estejam, provavelmente estão acostumadas a perder o e-mail de outras fontes legítimas também.