This is not 100% correct. If the other end already has a nonce, it can send the auth headers in the request and not be challenged.

True, but the cases where both sides already have a valid nonce will be rare unless there's been a recent exchange...