Update: It seems the authorization in question is not in pending and not in valid state (which it should be), when receiving the error Unable to update challenge :: authorization must be pending:
On the other hand, when a new Order is created, only pending and valid authorizations are reused/created:
So, one obvious explanation could be that there are multiple ACMECert instances running simultaneously using the same account-key and at least one common domain name. In this case they would share the same authorization(s), which then leads to this error (on the second slower instance). (It could even be on different servers running a cronjob at the same time for the same domain-names)
So I think I have found the cause. This happens when I try to verify DNS alltho the record doesn't exist. Yaac verifies the records using Cloudflares DNS over https api, and apparently LE servers have gotten quite alot slower (or have some changed dns caching settings / cloudflare got faster). My programm didnt check for this.