Larger companies have more money coming in which allows them to pay affiliate fees. If you have seen some of the prices they pay out just to convert one customer and then compare it to the price of their plans... You will see alot of the larger hosts actually take a loss for the first year to gain a client.
In the end, it's all really a numbers game. Some clients will stay, and some will leave but eventually I assume the larger hosts see a return on their investment.
For the smaller hosts, without the cash flow it's hard to offer the same affiliate deals that the larger hosts do. Instead, some choose not to offer any type of affiliate/referral program. Others choose to offer a credit towards the referrers hosting cost, a free month, or something else that won't require them to pay directly out of their pocket.
Alot of hosts do use cookies but obviously not all. I guess it comes down to what their developers can code up, what affiliate script they choose, or what a third-party provider offers them. And yes, Powweb does use cookies.