Atomz used to be the engine of choice (and was free for small-midsize sites), but I think they either just went under or there's not much support for it anymore. I'm not really sure what the deal is, but I know we're dumping it on a lot of our sites and thought I heard grumbling to that effect. I'd still check it out though if I were you.
As far as pay ones go most people would be inclined to say Google, but I personally don't think Google's algorithm is as well-tuned for individual sites. It relies FAR too much on link popularity to make it as useful internally. Granted, if you shell out the bucks for it you can tweak it extensively and probably diminish that weighting some. But for an out-of-the-gate paid solution Inktomi or FAST has the best algorithm for internal searches.
