I understand that its usually the payment service provider that charges for refunds, but in this case if you've been a customer for a year I would expect them to absorb that cost.

Clearly, you don't have any instances running in their Fremont datacenter. Hurricane Electric is like an unreliable, abusive alcoholic, and Linode is like a doting battered wife who stays with him because "someday he'll change".