Domain trust relationship failed

[Zagi]

Having an issue here at work with trust relationships failing regularly. I know the quick fix is to remove the PC from the domain and rejoin, but I need to find a permanent fix. Google isn't helping me much. I've even tried setting the machine passwords to never expire in the default policy. (Local computer policy > Windows settings > Security settings > Security Options > Domain member: Max machine account password age).

No deal, I hear about 1 or 2 PCs a day that the trust relationship has failed on. Anyone have an idea what to try, or something to check?

 

[Automata]

Are the computers still in the domain listing if you go look them up? I've only seen this when the DC thinks it is a different computer or it gets removed without leaving the domain.

If you have multiple domain controllers, could it be a syncing issue?