You don't say one way or the other, but are you doing all operations on a single database on a single server?
If so, you may want to consider using mysql's replication features. Set up a few slave databases, and perform all read-only operations (searches) on those, while writing to one master database (write operations then get pushed to all slaves). This will give you more available database connections, and also spread the load out between several machines. You can use round-robin DNS to determine what DB server to utilize at any given time.
I'd look at your indexing, as well. If you are having troubles with searches timing out, most likely you are not indexing the right criteria.