Yep, that's currently the way it works. Agreed that this may be more problematic in the DNS challenge, where propagation can take some time, than in the HTTP and TLS-SNI challenges. FWIW, Let's Encrypt always does authoritative resolution, so it's mainly about whether your authoritative NS has the record updated. For HTTP and TLS-SNI challenges, the client does a self-check before asking the server to verify. It would probably be worth doing the same in your client.
Also, definitely worth joining the IETF ACME WG and talking about changing / clarifying the protocol to allow some number of retries with the same token. You're not the only person who has requested something like that.
Correct, though to be very explicit, it's base64url, not regular base64.