Jakub, 

After doing some more troubleshooting I agree that there is no problem with having multiple kdc servers.
However, having more than one non-functional master_kdc is what's causing the failure.

server1 and server2 are down. server3 is up
this works.

kdc=server1
kdc=server2
kdc=server3
master_kdc=server1
#master_kdc=server2
master_kdc=server3

this will fail:
kdc=server1
kdc=server2
kdc=server3
master_kdc=server1
master_kdc=server2
master_kdc=server3

I've provided the log KRB5_TRACE output and it doesn't seem like kinit is even attempting to reach server3 if it sees that the first two master_kdc are down.