HI @voutasaurus,
I think we can disscount this hunch because the error message for a bad nonce is pretty distinct. The layer of the codebase that would raise a 400 for a challenge being the wrong state is beyond the WFE's check of the nonce.
You can send a GET request to the challenge URI that you are POSTing and it will have the status in the returned challenge object. It will also return a Link header with a rel="up" relation that will point to the URI of the Authorization object the particular challenge is associated with. Sending a GET to the Authorization URI will also include its state in the response.
Yup! That sounds likely. I think you're seeing the result of authorization reuse.
We just recently enabled this for pending authorizations. This was something we previously only did for valid authorizations.
I suspect that your system made two new-authz requests for the same identifier (let's say example.com). Maybe one request was made in Thread A and one in Thread B. If A is the first to POST new-authz for example.com it would get back a brand new pending authorization (let's say ID=abcd) for the identifier with a set of challenges. If B then subsequently POSTed new-authz for example.com it would get back pending authz ID=abcd. Now if A POSTs on the pending authz abcd challenges, and the Boulder VA is happy, the authz will get switched to state valid. If B comes along at this point and tries to do the same thing, POST one of the challenges, it will run into an error because the challenge is no longer pending. In fact the authorization the challenge is associated with is already valid and so none of the challenges are required.
Does that make sense? It may also explains why the issue isn't consistent. There are likely factors at work in your system that prevent this from happening in all cases.