IMO, if your market share is bigger than ${some number}, you shouldn't be able to deny service without a documented reason, it should have some sort of time-to-live (i.e 1 year), and there should be an appeals process. In a functioning marketplace, companies would be naturally incentivized to care about customers but that stops working in uncompetitive industries (which currently describes most of the economy).
... which may, indeed, be the right solution.