This has been going on for some time originally just with user machines after quite a bit of searching I never found the cause of the problem and was just rejoining the machines to the domain. I tend to find once it has happened to a machine it is more likely it will happen again.
Recently this has become a serious problem as servers have started to do the same. Domain controllers remain unaffected however when the exchange server refuses to it's computer account it is a serious pain!
I have tried removing the machine from the domain, ensuring that the computer accounts are completely gone then remaking the account and rejoining the domain. I can't really change the server names as this would cause too much trouble.
So far it seems to be happening it random some times the same machine will go twice in a week some times they will all stay happy for a month.
However when it does happen it will often be several at once.
I have one server at the moment experiencing the problem which I have deliberately left that way to try and trouble shoot the issue. The server it's self logged no errors just before it developed the problem. The DC's also show no relevant errors. The server is fully updated and antivirused. As are the other servers that show the same problem.
Any suggestions other than re-add to the domain are welcomed as that's all I've found so far.