I believe that some of the problems could be derived from how many topics that you have in each forum section of your board; I believe the UBB will start to go insane after about 10k (you should really think about an archive forum for old/dead threads).

Additionally the version of the UBB you're running is pretty old and there have been some updates to the search code, I'd definately reccommend an upgrade (you can find a changelog here).

I am a Web Development Contractor, I do not work for UBBCentral. I have provided free User to User Support since the beginning of these support forums.
Do you need Forum Install or Upgrade Services?
Forums: A Gardeners Forum
UBB.threads: UBBWiki, UBB Styles, UBB.Sitemaps
Longtime Supporter & Resident Post-A-Holic
VNC Web Services: Code Modifications, Upgrades, Styling, Coding Services, Disaster Recovery, and more!