Active Directory Time Error

The last 3 days or so random Macs from our 350 or so here have been falling off our Active Directory domain. When trying to unbind/rebind them Directory Utility tells me all about how AD "only permits slight variations between clocks on your computer and the AD server." This I know - Kerberos will only allow up to 5 mins difference between a workstation and the server. For this reason we sync the server (main domain controller) with a network time service, and sync all workstations and other servers to that server. This has never been a problem, and indeed works fine - the time on the workstation exactly matches the server time/time zone/date, etc.

So why is the AD plugin (and Kerberos) telling me that the clocks are out of sync when they patently are not?

This is happening with Macs of all kinds - 10.3 to 10.5, Intels, PPCs, everything.

My current workaround is to stop the Mac getting its time from the server, changing the clock by a couple of seconds, and then re-binding. This generally works. The odd ones that this doesn't work on, or that fall off the domain again within 24 hours, I've removed from AD and have given local logins to for now. I'm getting to the point where I just want to scrap AD integration and get every machine locally authenticating!

Our AD guys swear there have been no patches or changes on their end. I am equally certain there have been no changes to the Macs. So what could it be???