Why do I get "Server not found in Kerberos database" using testsaslauthd?

I’m trying to setup Kerberos auth over SASL using OpenLDAP. As I understand it, I need a host keytab in /etc/krb5.keytab from the KDC I’m using and then {SASL}user@realm in the given user’s LDAP password attribute. Switching users from root > nobody > user101 (with password) appears to work with a Linux KDC. Testing SASL via testsaslauthd is also succesful for user101 using the Linux KDC.

As soon as I switch keytab and server over to the production KDC however (2012 Server AD.MYCORP.COM below), I get Server not found in Kerberos database in the auth log. Some searching turns up possible rDNS issues as the culprit. I’ve added rdns = false in my krb5.conf and a few other settings trying to pin this down with no luck. I can get a forward DNS reply for AD.MYCORP.COM but the reverse does come back with a different hostname.

The windows admin sent me this error log with the closest timestamp matching the error in the Linux auth log. It seems to suggest an encryption algorithm issue, and not DNS. He is in the process of resetting the password on the service account but haven’t heard back from him yet:
While processing a TGS request for the target server
host/auth-test-ldap.mynet.net, the account [email protected] did not have
a suitable key for generating a Kerberos ticket (the missing key has an ID of 8).
The requested etypes were 18. The accounts available etypes were 23 -133 -128 18 17.
Changing or resetting the password of SVC-KEYTAB-MYNET2 will generate a proper key.

Is DNS most likely the problem? Any further way to debug on the Linux end? Config and logs using the Windows KDC and keytab are below.

/etc/krb5.conf

[libdefaults]
   default_realm = AD.MYCORP.COM
   krb4_config   = /etc/krb.conf
   krb4_realms   = /etc/krb.realms
   kdc_timesync  = 1
   ccache_type   = 4
   forwardable   = true
   proxiable     = true

   default_tkt_enctypes = aes256-cts-hmac-sha1-96
   default_tgs_enctypes = aes256-cts-hmac-sha1-96
   permitted_enctypes   = aes256-cts-hmac-sha1-96 aes128-cts-hmac-sha1-96 des3-cbc-sha1 arcfour-hmac-md5 camellia256-cts-cmac camellia128-cts-cmac des-cbc-crc des-cbc-md5 des-cbc-md

   rdns             = false
   dns_lookup_realm = false
   dns_lookup_kdc   = false

[login]
   krb4_convert     = true
   krb4_get_tickets = false

[realms]
   AD.MYCORP.COM = {
                   kdc          = ad.mycorp.com
                   admin_server = ad.mycorp.com
                 }

[domain_realm]
   .ad.mycorp.com = AD.MYCORP.COM
   ad.mycorp.com  = AD.MYCORP.COM

kinit with keytab and host principal works

# kinit -k host/[email protected]

klist the cache, looks ok

# klist
Ticket cache: FILE:/tmp/krb5cc_0
Default principal: host/[email protected]

Valid starting       Expires              Service principal
11/02/2020 09:10:48  11/02/2020 19:10:48  krbtgt/[email protected]
        renew until 11/03/2020 09:10:48

test user auth

# read -s PASS; testsaslauthd -u user101 -p $PASS -s ldap

/var/log/auth.log

Nov  2 09:11:07 auth-test-ldap saslauthd[714]: auth_krb5: krb5_mk_req(): Server not found in Kerberos database (-1765328377)
Nov  2 09:11:07 auth-test-ldap saslauthd[714]: auth_krb5: k5support_verify_tgt
Nov  2 09:11:07 auth-test-ldap saslauthd[714]: do_auth         : auth failure: [user=user101] [service=ldap] [realm=] [mech=kerberos5] [reason=saslauthd internal error]