Note that the option to flush CAA would only be present for DNSSEC signed zones (otherwise flushing a security-related record like CAA could be used to assist in a cache poisoning attack).
I am a bit surprised to see that Telekom uses Google Public DNS for this, since (for DNSSEC signed zones, at least) they need to verify the DNSSEC validity of the CAA response themselves (or use a secure protocol like DNS over HTTPS for their communications with Google Public DNS). If they are sending plain UDP to us and depending on the DNSSEC AD flag in our response, that is something that could be spoofed by anyone (quite easily for anyone who can see their queries to us).
If they are validating the DNSSEC, they presumably have a capable DNS resolver doing so, and could easily query authoritative name servers directly.
For domain administrators who are having this problem on a chronic basis, there is a simple solution, which is to reduce the TTL for the CAA record to something more reasonable, like one hour (3600).