1. Search isn't broken. We disabled it. *GASP*
2. We disabled it because there is a bug in SMF that indexes and searches forums that you don't have access to. The searching person wouldn't be able to go into the thread, but they could see the thread subject and the first few sentences from it.
3. Megiddo and I have spent some time trying to fix it, but no matter what we try it keeps bugging.
4. We ARE updated to the most recent version of SMF.
Last word from Megiddo on this issue is that he is going to try a clean installation of SMF and then restore the database to it instead of doing the incremental updates like we have been doing over the years. Something in an update might be broken that isn't in a clean installation.
I've tested SMF with a clean installation and this bug doesn't occur, so something is causing it on our installation.
I've tried disabling all of our plugins, but that doesn't help.
As JamminR posted in an above post, you can still search using Google and a little bit of google query magic.
We're working on the issue as we have time, and hope to bring the search feature back to the forum soon.
Sorry for the inconvenience and thanks.
P.S. Also, if you haven't noticed... JamminR has been a little nicer to people who ask questions recently.