2) If the transaction has inputs that conflict with another transaction in the memory pool, and it is the first such conflicting transaction, check the new transaction's signatures and if they're OK mark the memory pool transaction as "saw a double spend". Then relay the conflicting transaction (but don't otherwise remember it).
Rule (1) is to prevent an attacker from taking a bunch of her old, already-in-the-blockchain outputs and trying to generate a "double spend alert storm" by sending bogus double-spend attempts for them.
Two problems I see:
(A) I don't like the idea of giving the attacker more power.
For example, suppose the attacker has a connections to the main miners.
First he sends a small transaction to the network (or directly to a miner). This one travels fast.
Then he sends a double spend transaction of 100 Kbytes long to the network, with a high fee. Every node start relaying this double spend. As this transaction is huge, is travels very slow trough the network, consuming a lot of bandwidth.
The attacker is sure that the second one won't be included in a block because miners will reject it.
So miners should change the algorithm to choose the right transaction when a double-spend is detected: choose the one that pays more fees.
(B) How to allow a honest user to replace a transaction because of, for example, low fees specified in the first one?
You have to mark transaction in the pool to be automatically removed after some time, with some type of priority queue structure to allow fast search and removal of old transactions.
Marks in prevouts are lightweight, and easy to wipe out. Just erase them all every 10 minutes.
Best regards,
Sergio.