This seems to be a known issue. If leaving a host who also uses Cloudflare for DNS, we are unable to update the cached proxy’s IP. If I try to update it, nothing happens. If I turn the Proxy off, it works fine.
The problem is that there does not seem to be any way of resolving this with Cloudflare. The Community recommendation is to try contacting your old host. This should not be so.
The Community recommendation has actually been to use Liberate The Hostname for a while now. That may change as Cloudflare improves how churned hostnames are released. You can learn where to find the Community tool in the following Tutorial.