Since the fundamental problem is that mongos can send multiple requests to the same shard with startTransaction=true for a txnId, we might be able to fix this by adding another field to the txnId that is generated by mongos and transparent to the user. Then each time mongos sends a shard startTransaction=true, it can generate a new value for this field (transaction version?) that shards can use to distinguish the earlier attempts. This field could be scoped to a particular txnNumber, so the existing machinery for client retries on transient transaction errors would still work, i.e. any comparison of txnIds always compares the txnNumber before this field.
If we include each shard's expected version in the participant list and send it with prepare/commit (or every request within a transaction), we can abort the entire transaction if any shard has an unexpected version and return a transient transaction error label so the client can retry with a higher txnNumber, since this should only happen because of reordered messages if the client operates correctly.
We could even get rid of the aborts between statement retries by making shards treat a higher transaction version the same as a higher txnNumber and overwrite any state from a previous attempt.