Why would having a small MTU size make loging into Windows take 10 min?
I had a point-to-point link from a provider that did not have jumbo frames enabled when using QinQ tunneling and it made logging into Windows take 10 min, but the overall speed wasn't bad. Once jumbo frames had been enabled everything was really fast.
Does it have to do with framententing the authentication frames or something?
The article basically says that the Kerberos protocol initially tries to use UDP for authentication. The issue that you seem to be occurring in your situation is that when the UDP packets from Kerberos are sent over the tunnel, they are fragmented (because of the small MTU). When they are fragmented, they are lost (due to UDP's connectionless nature) and as a result this greatly delays the authentication process for Windows.
The article suggests changing a registry key on the client computer to for it to use TCP for Kerberos as this would overcome the issue presented by fragmentation.
I've had issues like this with VPN clients, and this solution has beautifully resolved those problems.
If the UDP packets are lost in transmission when they arrive out of order due to fragmentation, why does the sever ever get logged in? Does the server simply try over and over unil the fragmented packets happen to arrive in order?
I suspect either that or the Kerberos protocol has built-in capabilities to resend packets that it receives no acknowledgement on....not sure. I glanced at the Kerberos RFC and saw some areas where it indicates that clients must resend requests.