~30 days. Subject to change.
Yep, that's what you should do.
If you create a new order and see that it has one or more authorizations which are already valid, post {"status":"deactivated"} to each of them, and then re-create the order.
This will get you a fresh order without any previous validation history state.
(RFC 8555 - Automatic Certificate Management Environment (ACME))
You may find that, when using the test CA, it is helpful to deactivate all of your authorizations at the end of a test run. This saves you having to re-create your order the next time around - and you already have all the authz URLs handy.
There is a ceiling TTL of 60 seconds on Let's Encrypt's recursors. If both your CNAME and TXT record have a 1 second TTL, you shouldn't be having any trouble.
That said, I'm unsure about caching of NXDOMAIN responses. Does the problem still happen if you make a dummy/empty _acme-challenge TXT record a permanent fixture (so there's never any negative response for the query)?