Yahoo never had great search, they started life as a directory rather than a full search engine. Their first search functionality only searched their directory. Later they used Inktomi's crawler based search.
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.