Strange, all of those individual query times don't add up to the full mysql execution time. What you might try is during a slow period you can run the following from the sql command prompt:
SHOW PROCESSLIST
That will give you a list of the queries being run at that time and if any of them are locking the table. I'm guessing it could be related to the search which has some improvements coming in 6.5.
