I just want to raise the possibility of leveraging Google search (or any other search provider, for that matter).
Oversimplifying, you make sure that all your content gets crawled by the googlebot, then you just embed Google's site search widget in your site at appropriately.
The big issues are:
1. Make sure the crawler doesn't get lost.
2. Make sure the crawler doesn't overload your site.
Obviously, this doesn't work well for site content that isn't navigable.
Use the [color=#CC0000]3DOM50[/color] promo code for 3 extra lifetime domains and $50 off
More Dreamhost coupons here!