I've had an almost fanatic interest in Search Engines & Alltheweb was my favorite for a long time. In its heyday, Alltheweb had the freshest search index & best advanced search options. I guess this holds true even today. I procrastinated switching loyalty to the Big G precisely because of this. Alltheweb promised to index all the web (thus the name) & for a while seemed to be well on its way to fulfilling the promise.Alas, that was not to be! It was taken over by Overture (which also bought Altavista). Overture and Inktomi were then purchased by Yahoo! I don't know who provides the search results to whom, but Alltheweb's voice was lost in the din of the crowd, swamped by the mediocrity around it.
MSN Search is a bad joke & exists only for the sake of existence.
A9 (I'm sure you've tried it) is a quaint SE with lots of bells & whistles. It has even been clairvoyant enough to come up with its own searchbar for Firefox. It may be a force 2 reckon with if Amazon's maverick CEO doesn't screw it.
Addendum: Besides Google, Yahoo! is the only SE of substance.
Footnote: The most authoritative site on Search Engines is SearchEngineWatch. Its monthly newsletter is a must-have.