Legitimate senders
Hotmail are impossible to cope with from a legitimate sender's point of view too. I run a subscription based website and to validate accounts, customers need to click on a link in their email. I get almost daily complaints from Hotmail users claiming we haven't sent them their emails. I have the same problem with BT Internet addresses - and they don't even receive them in their bulk/spam folders, they just vanish, without even a bounce message back to me.
Requiring senders to cough up sounds a good idea but would wipe out legitimate newsletters and website subscription systems like mine. There's no way we could afford even a penny per email when we're sending out tens of thousands of emails a week.
I wouldn't mind some kind of sender verification system except that the general public are dumb and wouldn't be able to figure it out if they had to actually do something to be able to receive emails.