AD fails to authenticate some computer accounts

I have a problem where our AD randomly fails to authenticate some computer
accounts. When the user attempts to logon to their system and a domain
controller is available they are given an error message, when I check the
event logs on the DC the following error is logged: Source NETLOGON Event ID:
5805
The session setup from the computer Computername failed to authenticate. The
following error occurred:
Access is denied.
Also I get an Event ID 5723
The session setup from computer 'computer name' failed because the security
database does not contain a trust account 'computername$' referenced by the
specified computer.

When I remove the computers from the domain and rejoin the problem goes
away. Why would the AD suddenly not recognize a computer account? This
happens pretty frequently and the only fix seems to be to rejoin the domain.
Is there some security setting that could cause this?

Are these always the same computers that experience this?

If so it might be that the computer accounts themselves are corrupt. You can
test by removing the computer from the domain, delete the computer account,
then add the computer back to the domain and let the computer account be
recreated.

Thanks for the reply, its not always the same computer's that have the
problem, it seems random, perhaps it is just that some accounts are corrupt
but I am not sure why they would get corrupted.

By chance are you using F-Secure Anti-Virus version 5.3 on Windows XP?

Also what is the error listed in the "data" field of that event ID?

No, we use Trend Micro virus scanning, the data in the errors is as follows
0000: 22 00 00 c0

I'm facing the same problem specially after installing windows 2008 as AD in exiting 2003 environment does anyone can help me to solve this problem