Dado que o sudo em si só combina com as mesmas coisas que o atributo sudoHost menciona, estou inclinado a pensar que sem patch sudo intrusivo você não conseguirá o que procura.
Existe uma possibilidade - você está configurando o nome do host da máquina para o nome abreviado ou o FQDN? Se você estiver fazendo o primeiro, tente o último e veja se o sudo muda para reconhecer o FQDN (você provavelmente perderá a capacidade de combinar com o nome curto, no entanto). Honestamente, eu muito prefiro definir meu nome de host para um FQDN, acho que ele fornece muito mais valor em uma configuração de vários domínios como a que você descreve (que, a propósito, eu o aplaudo por fazendo, e eu desejo que todos façam isso).
Se eu fosse arriscar um palpite (educado) de por que você não pode (e honestamente, não deveria) corresponder com base no FQDN (ou, para ser mais específico, os dados fornecidos por hostname -f ) de hostname, eu diria que é porque esse valor ( hostname -f ) é obtido através do NSS - significando /etc/hosts ou DNS (e o sudo não sabe qual). Então, de repente, você tem uma vulnerabilidade de segurança em que, se um invasor puder manipular os resultados do DNS, ele terá sua configuração sudo restrita ao host pwned.
Como uma opção menos útil, mas ainda potencialmente valiosa (se a definição de FQDNs como o nome do host não for possível), alterne para o uso de endereços IP. É menos óbvio e um pouco trabalhoso de manutenção se você precisar renumerar, mas a menos que você esteja editando seus registros LDAP manualmente, sua sudo-config-maintenance-tool thingy pode pelo menos esconder a fealdade resolvendo nomes / endereços e dando-lhe nomes para brincar e sudo endereços IP.