In discussion with @marten-seemann he suggested:

Maybe the client could send a list of addresses it wants dialed, in descending priority. The receiver would pick exactly one of them and dial it

the proposal is:

Client has a list of addresses it wants to determine reachability for. In a dialRequest they send this list of address in priority order to the autonat server. The autonat server dials the first address it is capable of dialing and reports success or failure for that address.

This will be helpful in cases where we are interested in determining reachability for a newly address transport for which support in the network is low. Many requests for this new transport address will be rejected because the server cannot dial this transport. This proposal allows us to reuse those requests to check reachability for other addresses.

For some history this suggestion is an improvement over the scheme suggested here #538 (comment) . This scheme aimed to solve the same problem.