3) The recipient re-broadcasts transactions (is Theymos right here?), allowing both the sender and recipient to be found

Hm this would potentially allow getting the IP for any recipient Bitcoin address, given that a client with the private key connects to the network once in a while.

Send them a transaction that is guaranteed to not be written into a block by a miner, then monitor who rebroadcasts it over a few days/weeks.

I guess this could also be used to find out who has the stolen coins.

JS