Unless searches really have to be in real time, you might want to look into creating a second copy of your table for just searching, that will remain optimized and which only has searchable records (records flagged for deletion wouldn't be copied over). This secondary table would only have read requests, so it wouldn't have to worry about waiting on locks, and you could update it periodically (daily, perhaps).

Also, as mentioned above, the most important thing for optimizing searches is indexes. If you aren't using them, start doing so, and if you decide to stick with a single copy of your table(s), use OPTIMIZE TABLE often on tables that get a lot of inserts and updates - especially if they have TEXT or BLOB types.