MySQL is not the issue. SMF allows unlimited number of searches to be done. When you have 3.5million posts and then fifty to one hundred searches hit at one time, resources have a tendency to starve. Right now, MySQL is the throttle. I can reduce the resource usage of MySQL, but all that will do is bring on the same symptoms, more often, for shorter periods of time. I cannot up the resources of MySQL without detrimental effects on everything else on the server.
SMF has a poor search code implementation.
I have an idea I want to try, but it will require taking the board down for a few days to implement it.