As we don't know under what kvno a KDC stores our machine passwords we just use fantasy numbers when filling the in memory keytab with our (up to 4) machine passwords. If the kvno matches by accident the number we made up, the heimdal kerberos library may not fallback and check all other keys/passwords.
While we can't fix existing installs, why don't we store the KVNO? The (now deprecated) S4 member join codepath did that.
(In reply to Andrew Bartlett from comment #1) There's no reliable way to get the kvno and all ways that might work most of the time just add complexity without solving the problem.