Lol! I find a lot of this laughable.
(All in good taste, guys.)
If you want true anonymity on bitcoin, generate the coins yourself and spend them on digital goods (giving up shipping details would be counter-productive). If you don't have the CPU power, rent or buy more CPUs.
When all of the coins are generated, buy coins from one of your friends in person with cash. Mow their lawn for bitcoins. Whatever.
The ideal way would be to have exchangers in jurisdictions where they could easily accept cash in and out of the postal system. The reasoning for this is: no fees (besides a stamp), no banks to deal with, no 3rd parties such as paypal, it's anonymous, they can't claim 'commerce', OR subject matter jurisdiction over you. The value from the received fiat could be re-patrioted by mailing it back out to bitcoin users, purchases of goods in foreign markets that are sold online again for bitcoins/cash in a different currency/paypal, etc. (Really depends on what you are trying to achieve).
Courage always beats fear. Hands down. That said, exchangers need to be courageous. They need to know the law. They need to understand jurisdiction and commercial law (possibly property law and extradition laws as well) inside-out and backwards. If they don't, they are doomed to fail. I am talking from experience here.
If any of you think for a second that you can simply deal paypal/moneybookers/etc for bitcoins and not attract attention from the law (or those who provide the money transmitting services including banks) -- you are MISTAKEN. You may be able to run it for a while without attention, but it will happen eventually. (Again, this comes from experience.)
They try all sorts of underhanded tactics to defend the banking system. They'll demand that you need a license to be a money transmitter. They'll demand that you need a permit to operate within a particular city. They'll claim that you accepted cash proceeds from a crime and try you with criminal charges.
I've seen and heard it all.
It all starts with knowing the law and being courageous.
I wish you all the best.