In those days querying took some effort but the effort paid off. The results for "history" just couldn't matter less in this mindset. You search for "USA history" or "house commons history" or "lake whatever history" instead. If the results come up with unexpected things mixed in, you refine the query.
It was almost like a dialog. As a user, you brought in some context. The engine showed you its results, with a healthy mix of examples of everything it thought was in scope. Then you narrowed the scope by adding keywords (or forcing keywords out). Rinse and repeat. As a user, you were in command and the results reflected that.
The idea that the engine should "understand what you mean" is what took us to the current state. Now it feels like queries don't matter anymore. Google thinks it knows the semantics better than you, and steering it off its chosen path is sometimes obnoxiously hard.