The sender sends his BTC to the recipient with no fees (via the network). The recipient immediately broadcasts another transaction spending that money back to himself but this time including a fee.
What casascius said, AFAIK you can't reference a transaction if it's not in a block. The block chain establishes a timeline of transactions and each transaction builds on those in previous blocks.
That's not a problem though, it just means the sender will need to include the fees after all.
You immediately spend them back to yourself, but how many fees to include? If you include none I can mine a new block with my CPU and reclaim the coins.
You can't find a block on a CPU in reasonable time, fees have nothing to do with this.
If you include a 1 BTC/$ fee, each miner can afford to spend 1/1000th of a day (86.4 seconds) working on it before their costs would be higher than any potential gain. Because there are 10 miners each one works on it for 86.4 seconds in an attempt to find a block with that transaction in - probably not enough to find any block unless you get lucky.
The time to find a block follows the exponential distribution, which is memoryless. If it's profitable for me to try to solve a block now, it will still be exactly as profitable after 1000 seconds of trying. Nobody will suddenly stop mining after some arbitrary time, unless there's a mining police that monitors when someone tries to mine beyond the quota.
Also (a moot point in light of the above), if 10 miners each spend 1 BTC to try find this block, the total spent is 10 BTC which isn't covered by the fee.
What if you want two blocks? A 100 BTC fee would buy you 1/10th of a day (2.4 hours) of computation. The first block would be knocked out within a few minutes as the entire network tries to claim it. The second block would take much longer but would still be found as the miner who claimed the fees lives up to their end of the bargain.
And why would the miner want to work on a new block that has no fees? He's more likely to just say "I kept mining and didn't find any blocks. Honest."
And who does he report to anyway? The mining cartel police, or the sender who paid the fee? Does everyone who sends a transaction need to know the miner that collected his fee? Does the miner send difficulty-1 shares to the police to prove he's done his due work?
Also, someone who wants multiple blocks wants it in reasonable time, not the 100 minutes it takes to 1 miner out of 10 to find it, or the week it takes 1 miner out of 1000.
But in reality there will be many overlapping transactions. Let's imagine 30 mins after you send your tx somebody else does the same thing. Now all miners try to find a block including that second tx (including the one which was already mining to finish the work you paid for). A different miner claims the second tx and starts work. Now there are two miners working on securing your transaction .... but at some point your miner will shut down whilst the second keeps on going. The later transaction re-inforces the earlier but that's OK because it's not free riding - both senders are paying the same price for the same amount of work done.
I have no idea what your model is for multiple transactions per block. There are supposed to be thousands of them.
No miner would include free transactions at this point because to do so would immediately make lots of previously fee-paying transactions entirely free, yet that miner wouldn't get any greater share of the remaining fee paying ones. It'd kill their own bottom line.
Miners spend computing power to try solve a block, and choose which transactions to include in it. If they succeed, they collect all the fees for transactions they included. More included transactions = more fees = more revenue per hash = profit. The only way they would reject transactions out of fear of encouraging free-riders in the long term, is if they both expect their individual actions to significantly affect the market (which is suspect, given its size and complex dynamics) and intend to stay in the market long-term (which is even more suspect, given the low barrier of entry). See also
Prisoner's dilemma.
And what if the mining cartel uses FUD, vendor lock-in, lobbying and bullying to prevent people from forming an efficient market? Well, I thought that was one of the things Bitcoin was supposed to be against.