I like reading stuff like this. I deal with strange issues with MySQL all the time. It's nice to know others feel my pain and take the time to write about it. I don't usually see deadlocks anymore though thankfully.
Although we try to avoid deadlocks as much as possible at Yelp, retrying when a deadlock occurs is usually a viable strategy to take. Some deadlocks seem to be somewhat unavoidable.