Se realmente for um problema da parte da Outlook, não existe muito a fazer, já que será algo que é da responsabilidade dessa.

Pode tentar contactar diretamente o suporte da Outlook: http://answers.microsoft.com/pt-br/outlook_com/forum

Mas, fora isso, não existe muito mais a fazer...

Não possui outro sistema onde possa testar as contas? E outra ligação à internet?

Por exemplo, configure as mesmas contas num tablet/smartphone e tente proceder ao envio. Assim ficava-se com a melhor ideia se o problema é mesmo da Outlook ou da ligação do PC