your Windows clients are probably using NTLM (or NTLMv2), Microsoft's old, terrible auth protocol that the Windows team eventually abandoned for Kerberos. there are policy settings you can change to force Kerberos; I'd suggest Googling to see if you can find them, and see if it breaks your Windows clients as bad as your OS X clients seem to be.