As you asked you have multiple options. It just depends a bit what you're looking for. So let's see what's in the basket:
- Update the Plugin. - Either kindly ask the developer of the plugin to do so or do it your own. Often asking the developer is the best bet because he already knows it in and out.You might want to offer some bounty to the developer doing so. I mean if you used it successfully on your site and you like it, consider what's it worth to you. If you're looking for the best place to invest your money, you've found it. Contact the developer of the plugin and discuss the details of the problem. It pays to buy free software. Even I buy free software even I could extend it as well. It's just that you can't do everything on your own and most free software developers are very kind and do fair trades. If you've never done that, try it out. It's worth the experience.
- Update the Plugin (2). - If for some reason you do not want to contact the original developer or you can not afford it, you need to find someone else who does this. This would be either you or someone else. In any case, as you've used the plugin for so so long, if you get an update going for the current version, be so kind and pass it on to the original developer. If you think that's unfair as everybody else might get it for free, consider to find others who have the same problem like you and organize some funding. That even can be done fast enough and it can produce really cool results. It's not that it happens that often, but networking can be pretty effective.
- Switch the Plugin - If you're at the end of the road and you couldn't organize to get the plugin updated for some reason you incl. that you don't want to update it on your own (probably it's easy to fix? - I've seen non-developers who updated software that it worked again) then you must take a look for an alternative. Switching a plugin can be easy or can bear a lot of problems. It just depends. For your search plugin I must admit I have no clue. As free software comes with no strings attached, you're not bound to stick with one plugin.
- Downgrade your Site - A wise man once said ... bla bla :) Okay, here is the deal: Just do not destroy your site by blindly updating to the latest version. Wordpress 2.9 was a pretty good version, and it not only was, it still is. So before you upgrade your site, it's wise to check for compatibility before you update your live site. This can be done by creating a copy of it and updating the copy as a test. Well probably this is as complicated as hacking a plugin, but you can setup a second blog as well and just test for the plugins. That's a first step then. It's not that older software is badier per-se. Normally we not always need the latest and greatest.
I think the first two options you can and must decide on your own. For Point four this might be already too late, but wordpress pretty well downgrades as well.
Probably asking questions here helps to find others with the same problem. Which could help you in switching the plugin as well. I for myself can only give you these tips but not much more. I can not suggest you an alternative plugin because I don't know nor have I checked it's source why it's not working with 3.0. Normally that would be the first thing I've done, either to report that back to the original author or to just fix it and report it back as well. But you're free in your decision.