Indeed, they had an excellent search back then. But in a world before auto-complete in the URL bar, I wondered why they hadn't come up with a shorter and more catchy name. I usually was just too lazy to type "alltheweb.com", and I always had to think for a second to remember the URL in the first place.