Strange it is inconsistent. I’ve read before it may take a little longer for wildcard domains because of the DNS verification. Make sure you have the acme challenge record Fly provides, and that must be grey-cloud (non-proxied) in Cloudflare. Turning off Cloudflare’s proxy generally makes things a lot simpler when it comes to DNS checks as with that on, it returns Cloudflare’s IPs instead.
e.g this thread from someone else about setting up a wildcard domain which sounds similar:
I would guess if you are toggling Cloudflare settings that may cause a delay as the DNS would have to be re-checked at some interval (not sure how often). So I’d recommend adding the record with a grey-cloud then request the certificate. So when it’s checked, it won’t return a Cloudflare IP.