Why isn't a dependent transaction which pays a fee all that is needed? This requires no dropping of existing transactions.
1. A+B -> C + D
2. D+E -> F + (G - Fee)
In this case the Fee pays for both transaction 1 and transaction 2.
A zero fee transaction won't propagate and neither will one that collides with another transaction. If you have a rule that higher transaction fee transactions that have all the same inputs and outputs replace the older transaction, then it doesn't matter if the node has seen the earlier transaction or not, it will propagate.