Maybe I misunderstand the problem, but assume Mallory submits an old state, Alice submits the newest state in the mempool, but Mallory can outbid hers with any of the previous states. If you use a TXID dependent form of fee paying mechanism Alice has to re-sign each and every time this happens. Her rebindable signatures are still good ofc, just the transactions are ejected from the mempool.
CLRT does not really mitigate this afaik, in fact makes it more dangerous.