As I remember it, the "highly relevant" results on Google were almost exclusively determined by a $299 Yahoo! Directory listing or a DMOZ directory listing. If you could get the Yahoo Directory or DMOZ to link to you with your preferred anchor text - you were all but guaranteed the #1 spot on Google. Of course it didn't mean as much back then, but boy was it easy.

This brings back a lot of memories. Like you said, Yahoo! was referring all of the traffic. For those of you that weren't around or don't remember - the Yahoo Directory was based on the alphabet, like the phone book. I had to beat out AAAUsedLaptops.com with exclamation-point-used-laptops.com (listed as "! Used Laptops"). No wonder Google won.