Você meio que tocou no seu comentário acima; Basicamente, a primeira coisa em uma conexão é emitir um comando HELO (smtp) ou EHLO (esmtp) do cliente para o servidor. O problema é que, agora, você não sabe o que o example.com tem em seu arquivo de configuração de mensagens.
O que eu faria para depurar é configurar seu próprio MTA (exim, postfix, etc.) em um servidor em algum lugar e aumentar a saída de log para capturar seu cliente normal e suas sessões de envio de aplicativo java e comparar o que cada MUA é enviando para o servidor, especialmente aquele campo HELO / EHLO. Alternativamente, se a configuração de um servidor de e-mail rápido for demais para você, você poderia usar o tcpdump no host e capturar os pacotes brutos de saída e visualizá-los no Wireshark para ler as cargas úteis.
Como exemplo, aqui está a configuração padrão do Exim fora da caixa em relação a essa informação:
# Hosts are required to say HELO (or EHLO) before sending mail.
# So don't allow them to use the MAIL command if they haven't
# done so.
deny condition = ${if eq{$sender_helo_name}{} {1}}
message = Nice boys say HELO first
# Use the lack of reverse DNS to trigger greylisting. Some people
# even reject for it but that would be a little excessive.
warn condition = ${if eq{$sender_host_name}{} {1}}
set acl_m_greylistreasons = Host $sender_host_address lacks reverse DNS\n$acl_m_greylistreasons
accept
Você também pode verificar se o seu aplicativo Java está usando o mesmo tipo de autenticação do seu cliente regular - talvez seu servidor de email reaja de maneira diferente se um estilo PLAIN ou LOGIN for usado em vez de, digamos, CRAM-MD5. Isso é de responsabilidade exclusiva do administrador do MTA, então novamente você está à mercê deles.