What were once vices are now habits.
This 1999 article from Salon mentions that Alta Vista was considering adding paid relevant links. I was working with the Open Text Web Index a while before that and we considered and rejected the same idea, believing that it would destroy the trust our users had in us. Boy were we wrong! It's amazing how this has become such common practice now.

