Bem, você tem o FQDN correto e o Exchange Online não bloqueará o acesso de entrada a esse FQDN na porta 25 por padrão, para que ele possa aceitar emails de entrada de qualquer domínio do remetente (email normal).
O fato de você poder fazer o ping dele, e que você pode chegar lá a partir da sua rede local, significa que é mais provável que seja do lado do servidor onde está o problema.
Então, se esse é o caso, você tem algumas possibilidades, algumas das quais são:
- Possível firewall de saída no lado da LAN / WAN do seu servidor da web. Pode enviar e conectar-se a outros servidores de email na porta 25?
- O ISP / conexão do servidor da Web não permite a porta de saída 25, a menos que você passe pelos servidores de e-mail. Isso é feito tipicamente para os ISPs domésticos, mas alguns provedores de negócios podem evitar isso também. Você teria que verificar com eles para descobrir se este é o caso.
Portanto, a partir do que você descreveu, não deve ter nada a ver com a sua própria conta do Exchange Online, mas tudo a ver com o lado das coisas do seu servidor Web.
Como discutido nos comentários abaixo, se o seu VPS no Godaddy bloquear a porta de saída 25, retransmita através deles (o que é fácil o suficiente ...) ou use a porta 587 para smtp relay usando smtp.office365.com.