Hi,
I think Tim's Google trick is really cool and until we have a better search engine ourselves, we should definitely put a search box like his on our home page.
The only downside is that Google indexes our site only once a month.
On my sites, I have in the past used http://htdig.org. The search results are just as fast and precise as google's, but you control when and what you index. A cron script once a night should be fine.
Axel