I ran into the same error... I suspect that it's because I'm using a mix of private and public Azure DNS entries and the record needs to get added to the public entry so letsencrypt can see it, however, cert-manager performs a check that the TXT record is visible before asking letsencrypt to perform the validation... I assume that the default DNS records cert-manager looks at is the private one, and because there's no TXT record there, it gets stuck on this error.

The way around it, as described on cert-manager.io is to override the default DNS using extraArgs (I'm doing this with terraform and helm):

resource "helm_release" "cert_manager" {
  name       = "cert-manager"
  repository = "https://charts.jetstack.io"
  chart      = "cert-manager"
  
  set {
    name  = "installCRDs"
    value = "true"
  }
  
  set {
    name  = "extraArgs"
    value = "{--dns01-recursive-nameservers-only,--dns01-recursive-nameservers=8.8.8.8:53\\,1.1.1.1:53}"
  }
}