É possível que o ISP de usuários japoneses esteja bloqueando conexões de saída de usuários finais na porta 25 para forçar o correio através de seu servidor de e-mail e, assim, reduzir o spam. Você já tentou abrir uma porta alternativa (587 - Submissão) é normalmente usado para enviar e-mail para um servidor SMTP ou para a porta 465 para envio via SSL.
Na minha parte do mundo, ocasionalmente, a porta 26 é usada para executar o mesmo que a porta 25, exceto para contornar o maior bloco regional de ISPs.