The logs have been reviewed for every time the error occurred. At none of these times there were MySQL restarts. No high server loads and no full memory either. Meanwhile the same error keeps coming in. So something is going wrong with that query. Its quite a mystery.
The only thing we can think of is upgrade MySQL to 5.5 and hope its gone then.
Please let me know if you or Michael have any ideas / suggestions.