> 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.