Got it finally working by re-creating /etc/krb5.keytab file from the scratch.
It turned out, that I did not use Samba to join the machine to AD, but I used Centrify.

There is nothing wrong with that, the only thing is, that unlike Samba & SSSD, Centrify does refresh principals in /etc/krb5.keytab creating multiple principals in keytab that differ only by the KVNO number.

This is nice, but both sshd & pam_krb5.so seem to totally ignore KVNOs, picking the first principal they find in keytab.

So I am going to file RH bugzilla report

Ondrej