How long had your mysql server been up when those stats were taken?
You are correct about the search being the bottleneck, it's the same with most bulletin board software. I've recently written a search modification to disallow certain words that are very common on our board as well as requiring that the search term is at least 5 characters.
Donate to UBBDev today to help aid in Operational, Server and Script Maintenance, and Development costs.
Please also see our parent organization VNC Web Services if you're in the need of a new UBB.threads Install or Upgrade, Site/Server Migrations, or Security and Coding Services.