I've run into the same error where I work, and while this may not be the case for you, maybe it'll help.

The problem was, the users getting this error (not linked servers, but SQL logins) had been away for some time, and because of corporate policy, their AD accounts deleted. When they came back, new accounts were created, but the SPIDs (obviously) had changed, so they couldn't login.

Now, in your case, my thoughts are (based on what you've posted so far:)

1. Are the machines at different ends of a "slow" connection (VPN, etc)? If so, it could be a domain replication issue, which is why it works sometimes, or just a corrupted packet during the authentication.

2. If not 1, possibly a "flaky" connection or a slow response from a DC?

Just a couple thoughts. I'd lean towards it probably not being the SQL, though...

Jason

*****************************

I'm sorry, I missed where the account is NT Authority\Anonymous

I'm not sure my thoughts will be applicable, after all.