First, you should be aware that there's no such thing as a canned search. There are various types of searches for various purposes. Some go well into six figures (e.g., when 7, 8 or more figures are at stake in a litigation). Other searches are merely dipping your toe in the water to see if you can find anything quickly that would be an obvious impediment to getting strong IP protection from your patent application. And, there's a continuum of scopes and commensurate prices between those extremes.
In addition, there are generally two parts to the search. First, there's the search itself -- justing collecting things that might be relevant. Second, there's the analysis of what you found -- do those things leave sufficient room for a valuable IP asset?
For the first part, I've used SCI3 in Sunnyvale, CA (
http://www.sci3.com/) with good results. Ideally, Marjory prefers to just help others do their own search, but SCI3 advertises searching services for $120/hour with a 2-hour minimum. That's what it was last time I've checked. I'm not sure Marjory is still there.
There are a number of others who will perform a perfunctory first-stage search for various costs -- some in the general ballpark of what you paid in 1999. Many will charge over $1,000 for the same thing -- well, not perfunctory, but just the first stage.
It's fairly hard to get a good second stage included for less than $1,000. And, if you skimp on stage one, you'll pay for it in stage two. One of the great value-adds of a good search is the ability to filter out the "looks relevant at first glance but really isn't" category of references. That saves time and considerable expense at the second stage.
And, the hidden factor of any search is the likelihood that something important was not found. There's really no way to assess that, other than to hire a couple different searchers and compare results.
I know it's a cliche, but you get what you pay for. You really have to compare your budget with what you hope to achieve in the search -- and how tolerant you are of risk that something important remains unfound.
Regards.