It's hard now when Google have their market position. For Google it was easy to grab the low hanging fruit.
I wonder if former competitors like Altavista just never though of spying on their users and selling the info or if they assumed it would be illegal and didn't do it?