A double-spend would be pretty easy if the purchase transaction was sent without a fee, then the double-spend transaction was sent with a standard fee.
You make a very important point.
Currently the majority nodes on the network use code that will not replace a transaction with another one under any circumstance. However, if fees were a major source of income from miners, it would make sense to mine the highest fee transaction the miner knew about regardless of whether or not it replaced a previous transaction with different outputs.
If even one or two miners/mining pools start implementing this, perhaps under the guise of allowing people to easily "adjust" the fees of their transactions, all the assumptions about the difficulty of getting double-spends mined will change overnight.
Of course, we do have a weapon against mining
pools: given the infrequency of target-meeting PoW solutions a hasher can easily change their hashing setup to fail to send the shares that happen to meet the target, thus cheating the pool operator out of the block and effectively stealing all the shares. P2Pool combats this with a 0.5% reward to the block finder, but it's easy to see how a pool identified with double-spends could be attacked.
However you can run a "pool" in a different way; call it a "Block Opportunities" service. Now the service simply gives each hasher a work unit that pays the whole coinbase to the hashers chosen address. If the hasher withholds the solution, they've just wasted their effort. Of course it gets rid of the variance reduction that pools provide, but the long-term profit is still the same. I'm sure there are lots of hashers with setups large enough to consider essentially mining solo with such a service in exchange for the higher reward, not to mention it can obviously be done in a decentralized way as well by modifying the Bitcoin client to preferentially connect to other nodes with a simple "max-fee-wins" policy.