A double spend alert could be constructed so that it actually wasn't useful for replace by fee. E.g. you package up the input, scriptsig, and masked hash. Beyond not enabling other people to mine transactions you don't like much this would make the alerts smaller when there are more outputs than inputs.
On the downside, it would make distinguishing a benign replacement from a malicious one on the basis of the alert impossible.
Ideally, the transactions should be timestamped, and the first one sent should be placed on the block chain. I suspect that this would allow for a timestamp attack, however.