> There are a lot of hidden pitfalls in bitcoin security (such as - the above isn't guaranteed, if miners change their mind to be greedy and pick the transaction with the highest fee instead of the first one, that method breaks) so I'm not sure if it's bulletproof though.
Keep in mind that enabling this also opens up a counter-attack, against double spending: if User A sends 1 BTC to you with a fee of 0.0001 BTC, and you discover that, after sending this transaction to you, he sends the same 1 BTC to another address, this time with a 0.1 BTC fee, you can create a new transaction that spends the 1 BTC originally sent to you (with the 0.0001 BTC fee) which spends everything as a fee in this new transaction.
This way you don't actually get the money, the miners do, but you punish double spending. And if miners are greedy - and want to include whichever transaction makes them the most money - they will want include to include yours, as this makes them a whole 1 BTC in fees.
So in the end, while it may seem that miners including the highest-fee transaction increases the risk of double spending, it might actually prevent it, since merchants will also gain an effective way of punishing it.
Is this actually possible? You couldn't change the original transaction without the private key, nor can you spend the results of it until it is in an accepted block chain block, no? Am I wrong?
You can broadcast a valid tx that depends on an unconfirmed valid tx that was already broadcasted. The second tx will only be confirmed if the first is, this is how betting sites that accept 0conf txs (such as SatoshiDice) work.
Not sure if pool software currently selects txs as a sum of the fees of the txs that depend on them, but it seems reasonable to implement.
Keep in mind that enabling this also opens up a counter-attack, against double spending: if User A sends 1 BTC to you with a fee of 0.0001 BTC, and you discover that, after sending this transaction to you, he sends the same 1 BTC to another address, this time with a 0.1 BTC fee, you can create a new transaction that spends the 1 BTC originally sent to you (with the 0.0001 BTC fee) which spends everything as a fee in this new transaction.
This way you don't actually get the money, the miners do, but you punish double spending. And if miners are greedy - and want to include whichever transaction makes them the most money - they will want include to include yours, as this makes them a whole 1 BTC in fees.
So in the end, while it may seem that miners including the highest-fee transaction increases the risk of double spending, it might actually prevent it, since merchants will also gain an effective way of punishing it.