Yahoo has been doing these "Search Distribution Deals" for many years, as long as I can remember in fact. Bing was at one point paying $20+ per toolbar install when they were trying to gain market share. Google has done paid toolbar distribution as well.
The reason it is still around is because it is so damn effective.
The reason it is still around is because it is so damn effective.