Yeah, the machines themselves unfortunately must delegate, but as you mentioned it's inconsistent. However, the error itself is still a Kerberos baseline.

You're most likely going to have to drag in one of your network guys on this, and he'll probably have to run Wireshark or something equivalent to try to bag one of the errors when it comes in. That'll give you a lot more information.

I wouldn't troubleshoot the linked server in this case though, unless a particular account or two are the usual culprits. I'd be troubleshooting the network. It could be anything from it using a switch that's across a domain (incredibly unlikely) for traffic routing to something goofyfoot in the accounts that it's using cached data on occassion. I don't know, I'm definately NOT a network sysadmin expert. I do recommend getting one involved though.