Maybe you're right that ultimately they were not on the correct plan and Cloudflare was right to make them move. I don't know enough about Cloudflare's different plans to say. But what I do know is that:

When we told them we were also in talks with Fastly, they suddenly "purged" all our domains

Is utterly indefensible anticompetitive behaviour. So is a 24 hour ultimatum for a 40x increase in cost. I don't care if they were on the free plan and should have been on enterprise. If the ToS violation isn't actively causing harm to the public, any adjustment should be done with sufficient notice that arrangements can actually be made. 30 days seem s reasonable.