When your ACME client POSTs a challenge associated with a pending authorization for a domain Let's Encrypt performs an initial CAA validation request for the domain alongside the challenge validation request.
Since as @tob mentions (thanks!) we are also required by the baseline requirements & RFC 6844 to check CAA within 8 hours of issuance, we also may have to recheck CAA for a name at the time of issuance when the valid authorization held by the account for the identifier was validated > 8 hours ago.
In this case since the error message was prefixed by "Rechecking CAA:" we can tell this second condition is what happened. Your issuance was likely using a previously validated authorization (recall that valid authorizations are reused) that was validated more than 8 hours ago, requiring a CAA recheck that failed the issuance.
We do check CAA before the DNS challenge is completed for the initial pending authorization. Hope that helps explain things.