Good point - transactions can be ordered by highest version seen before they're signature checked. Even without that improvement it's still rather tricky to win the race though.

I'm intending on making a prototype for myself at some point soon, probably in bitcoinj. I've been making notes and writing some initial code - I did successfully replace a transation on my own little testnet, then I figured I'd submit the patch so it's easier for others to play with it. But I haven't got the whole thing working end to end yet.