I just happened to see this right before I read your post. The “deadlocking” servers part of that description sounds similar enough to your issue that you might want to take a look at it.
Normally my first guess with your problem would be a corrupt database but you said you checked that
