Indeed, Bitcoin offers just pseudo-anonymity. However, if you are very disciplined, you can severely limit or even totally remove the possibility of someone linking you to your Bitcoins. No one even needs to know a transaction happened in Kenya.
I'm curious how you might do this? Basically you must be able to hide the fact that you own an address, correct? Does that mean using different addresses for handling transactions while updating the block chain from different IPs (in different physical locations, just so your phone or simple general geographic pattern doesn't reveal you)? Is there something I might be missing?
Another problem you hint at is broadcasting a transaction from certain IPs. A common heuristic is to record the IP of the first node to report a transaction as the node that made the transaction. You would have to modify your client so that is not the case, or use some sort of VPN to connect to the network.
The payee would just check the balance of the associated public key before the transaction and immediately transfer the balance after the transaction.
If you want to know how to achieve this, look to modern money laundering practices.
That would make the protocol useless for day to day transactions like buying groceries, but at least as anonymous as cash for more sensitive transactions.
Exchanging private keys is fraught with peril- the originator doesn't lose knowledge of what the key was when they give it to you. The only way to make it work safely is to immediately transfer funds out of the key you just received (to ensure the originator doesn't pull the funds before you can use them), and then we are back to having a trail. As far as someone following that trail is concerned, it is just an extra "hop"- the money still flowed from IllegalVendorA to <unknown> to You.
You can certainly try to obfuscate things, but the point is all the data is there and always will be, and even if it seems like a human wouldn't be able to figure it out, computers are very good at working through graphs!