It seems that in gaining over 100,000 players, Kevan’s Urban Dead game has managed to find a bug in MySQL that causes corruption of indexes. Unfortunately no-one at MySQL AB is able to replicate the bug so it can’t be tracked down and fixed.
More information can be found in the MySQL forum.