I think you're right, and defraud is the wrong word, because fraud implies malicious intent. However, that's almost beside the point - many customers paid for the product that was advertised/documented and received something completely different. Whether or not it was intentional, it should be remediated rather than painted over.
Let's completely ignore the random vs. intelligent routing question for the moment and just talk about the New Relic analytics add-on. Heroku customers were paying ~$40 per month PER DYNO for this service. One of the most compelling things about New Relic is that it not only tracks average request time, but also breaks down this data into its components so developers can see which systems are slowing down their requests. Not only did it fail to report the queueing component, it failed to account for it in the total request time, meaning both values were wrong and basically useless.
I don't understand how Heroku can admit that the tools for which their customers paid obscene amounts of money were completely broken for two years straight and yet do nothing about it besides apologize. The fact that most customers did not realize it was broken does not mean it didn't cause real, tangible harm to their businesses.
It's hard to draw an analogy here since it's rare to use a product for so long without noticing it's not what you paid for, but I'll try - imagine you lease a car for two years. You can pay $500/month for the standard model with n tons of CO2 emissions/mile, or $800/month for a hybrid model with n/5 tons of emissions. You opt for the more expensive hybrid, but after driving the car around happily for two years, you pop the hood only to find that the company gave you the standard model. After complaining to the company, they apologize and give you the standard model. Wouldn't you expect them to also retroactively refund you $300/month for every month you paid for a product that you didn't receive? Does the fact that this was a genuine mistake, rather than an attempt to defraud, change your expectation for receiving a refund? It certainly wouldn't for me.
Fair enough, and good analogy. As you said it's hard to make comparisons between physical goods and a metered software service.
The New Relic question is tricky. The free version of NR includes queue time, so that implies that the incremental value you're getting from the paid service does not include this. I'm also not sure how "this product you've gotten for free has a bug" fits into this equation. But overall, yes, NR is a product that is designed to give you visibility, and due to incorrect data being reported, some of that visibility wasn't there.
Therefore, we've given credits to people who have had substantial financial impact of the sort you describe. There aren't very many in this category and I believe we've already covered them all, but if you believe you're in this category please email me: adam at heroku dot com