I think we were suffering from a bug. First symptom on the server is huge amounts (ca. 140 per second from one client alone) of Failed building TGS-REP in kdc.log on the (heimdal) server.

We allow long ticket lifetimes (1 year) on the Kerberos server, but the client still orders 1-day tickets. That is remedied by setting ticket_lifetime in /etc/krb5.conf on the client:

[libdefaults]
ticket_lifetime = 31536000
<snip>