Alice receives the BTC from teh exchange on address A1. She transfers from A1 to A2, sends the private key to Bob who can then transfer from A2 to B1 and then, to the exchange through an address B2 that is tied to him. So there is still a link between Alice and Bob.
Alice sends the private key to Bob using Tor or i2p or whatever. Nobody sees this. If there are intermediaries (such as in my last posting) it gets just better. Think of it as a remixing cascade for bitcoins, if you wish.
If Alice uses the bitcoin client to send money to Bob, everyone sees it in blockexplorer.
If Bob creates a fresh address and Alice sends money to it, nobody is going to know it's Bob's address until he associates himself with it. He could create it offline and it could never have been seen by the network. You already can't get more anonymous than that and there is no need for Alice to know the PK. Whatever you do, though it can be made obscure, the transaction will be somehow linked to Alice through the exchange records.