After reading the KRB5_TRACE logs I have a strong suspicion. The servers
DNS entry is an A record on a loadbalancer IP address. This IP address
does also have other (completely different) A records. And the krb log
looks like as if these A records get mixed up in some cases.
Does this make sense to you?
Cheers,
Ronald