Who's at fault?
Part of the problem is that the domain issuing companies allow for the purchase of large blocks of addresses and then allow the purchaser to cancel their orders without being charged. Even if they only allow them to claim a refund within 24 hours, by then they have sent millions of spam messages using those addresses!
Maybe they should charge a few cents per address, just for them being assigned. This would be a minor burden for the legitimate businesses, but would start to put a dent in the spammer's piggy banks...