Simply knocking out unconfirmed tx from memory pool by another higher fee variant would enable the payor to cancel any payment before included in a block - by double spending to own account. This is a no-go.

I also think that block inclusion would better be simple fee/size order and that memory pool should expire somewhat faster than current 3 days.

The thing about Bitcoin is that you can't rely on good behavior in the nodes. Just like there were griefers who set up tx mutation nodes for the hell of it, there could be nodes that are programmed to make double spending of 0 conf transactions easier.

Merchants need a better solution than "hope adversaries decide to play nice".

Maybe something along the lines of pools offering subscription services via which a merchant can obtain assurance the pool will not mine a conflicting transaction.

This has been debated endlessly.  It comes down to whether the expected losses from double spends are significant to the merchant's bottom line.  

Purchasing a latté from Starbucks is almost certainly fine, while purchasing 100 oz of gold will definitely require a few confirmations.  Purchasing $300 of groceries (low profit margin business), well, we'll have to see how the double spend statistics look.

Remember, the expected loss due to double spending on zero-confirm transactions is:

(% expected loss) = (% of people that will attempt to defraud you) x (% of global hash power controlled by fraudulent miners)

In a retail setting, I expect less than 5% of customers to attempt to defraud the merchant, and I expect less than 10% of global hash power to be nefarious. This gives an expected loss on zero-confirm transactions of less than 0.1 x 0.05 = 0.5%.  


EDIT: do you know of any mining pools that control a significant fraction of global hash power that current accept out-of-band knowingly-fraudulent transactions?

Ghash.io has been caught with their hand in the cookie jar. Other cloud mining operations that are coming online soon have the capability to do this with limited risk to themselves. A further 15% of the network is not identifiable and therefore would be able to do this with plausible deniability.

"Knowingly fraudulent" is not a phrase I would use. There is no way for 3rd parties to know with certainty which transaction came first, and therefore which one is the fraud. It's the nature of the bitcoin consensus system.

It was double-spends / rerolls against BetCoin.

"ghash.io betcoin" in google should get you some results.

I do not think one can call a miner fraudulent if prefers a transaction with higher fee/kb above a lower variant. It is their freedom to mine whatever transactions they choose to.

The relay nodes are also free to relay or reject whatever they like. It is however beneficial to the network as a whole if relay nodes do not replace transactions with their double spend of a higher fee.

Nowadays relay nodes are quite homogenous and do not replace transactions, therefore unconfirmed double-spends are usually not making to the miner, this could however change. I guess merchants will feel the pain if so, and adapt.

 

A miner also has the freedom to walk out on the street and kick some random guy in the nuts.

Just because a miner is able to replace a lower-paying transaction with a higher-paying variant, doesn't mean that doing so is not fraudulent in certain cases.  Most societies have laws against fraud and for good reason.  A common definition of fraud would be:

    fraud: wrongful deception intended to result in financial or personal gain

If a miner knowingly runs a service that accepts out-of-band double-spend transactions, then in most (all?) cases the purpose of doing so is fraudulent.  Typically, these miners would be accepting the transaction for a higher fee, from a user trying to deceive a merchant.  If this can be proven, then it's fraud.  If bitcoin gains widespread acceptance, I expect law enforcement to respond, making it difficult for this type of behaviour to flourish.  This, and social pressure to behave ethically, I believe will keep bitcoin fraud on most zero-confirm transactions below the loss percentages due to counterfeit bills, stolen credit cards, or chargeback fraud.  

That being said, I believe I do understand the bigger point you are making: the network can change and miners and nodes might not behave in the way we expect.  I agree with that statement.  Still, the risk of accepting zero-confirm transactions always comes down to the excepted loss statistics at that time.  But at least right now, I can walk down to Central Bistro in Vancouver, eat an expensive dinner, pay via BitPay, and leave before the first confirmation has arrived.  So far it's working.  

Consider two different scenarios:

a) A fraudulent customer pays for a product and broadcasts a double spend with higher fee.
b) A poorly written wallet sends a transaction with excessive fee, the developer notices and attempts to double spend it with a lower fee variant.

A miner receives any of the above transactions through relay nodes in random order. Which one should he chose to remain honorable?

Another way to get more comfort at local trade is to observe network propagation. The merchant can connect to a high number of nodes and observe if all of them echo the "right" transaction.

But observing propagation does not protect from a fraudster with a big miner buddy and is vulnerable to network isolation/siblings attack.

I think as the network matures merchants and their software will learn to combine evidences to a degree of trust. At the end nothing beats what is on the block chain, so for certainty one has to be patient.

To sum up:

The order of transactions is exactly the problem that bitcoin was invented to solve.

The order presented in the blockchain is the only order with any meaning.
 - If you disagree with the order in the blockchain, you are wrong, not the chain.

If you are relying on the order of things not yet in the chain, you are wrong.
 - Bitcoin is not a coercive system.  No one can stop you from being wrong, but you do so at your own risk, and inevitably to your own peril.

If you have an opinion on what order things should be in when they are eventually included in the block chain, you are wrong.
 - Even if you guessed right.
 - Bitcoin is not a coercive system.  No one can force a miner to prefer any ordering over any other.


Not that one can't or even necessarily shouldn't take risks based on undefined future ordering.  The real problem is that some people don't understand the risks they are taking right now.  The network is fairly polite right now and it usually does what you think it will do.  But that politeness is not a property of the system, but an accident of history.