Estou perguntando e respondendo caso outras pessoas encontrem esse problema ...
Acontece que depois que instalamos o SP2 para o Windows 2008, o FQDN configurado nas configurações de SMTP é redefinido para o nome do servidor, em vez do nome de domínio totalmente qualificado que criamos originalmente.