I don't know if there is a universally "correct" way to handle this issue.
In our system, we always, always respond with a Gap Fill, i.e.
Exchange: "Hey, we're missing sequences 537 through 542!"
Us: "Don't worry about it. Expect sequence 545 next."
The 545 is not a typo—we may have already sent 543 and 544 while their Resend Request was in transmission.
This technique is expressly to avoid the kind of dilemmas you're facing. By refusing to send old messages, you at the very least retain control over your executions.
To illustrate a larger perspective, what we do is, when we initiate any action on an order, we flag the order as "in progress," meaning it cannot be actioned further in any way (amended/CFO'ed or cancelled). Only when we receive an ACK, i.e. an Execution Report, do we remove this state. So if the exchange misses a message pertaining to that order, that order simply ends up "stuck" (and gets highlighted as such on the front-end). Not ideal, but again, at least it's not out of control. The trader then simply re-enters the desired order. (Note that it's the very guarantee that we won't resend messages that enables a trader to safely re-enter orders.) With our system it's just try-again-and-move-on, without need for complex sequence-scenario resolving.
Source: Work on an order entry system connecting to >10 Canadian exchanges, used by >50 Canadian brokers.