There has been a lot of attention recently to the arrest of an alleged LulzSec hacker after his anonymity was compromised by the anonymity service he was using, HideMyAss.com. Some articles on the event are here, here and the provider's explanation here. The reason this company was able to compromise the privacy of their user was that they had logs of user activity. They know what IP address is assigned to each user and can use that to attribute any activity back to the real identity of the person behind the account.
The real problem with logs is that they exist or they don't. You can't keep logs only for "bad users" but not for responsible "good users" because even if it was possible to identify them as such in advance, you would not find anything like agreement about who should fall in which category.
Many operators of privacy services, including myself, feel very strongly that such tools should be usable in countries like China to circumvent the censorship and surveillance there. Such actions are certainly illegal for the user, and probably for the provider. While being a UK company and only responding to UK court orders, they were "forced" to expose the identity of a person in the US who was then arrested by the FBI.
I don't know enough about this case to debate whether or not this person is guilty or deserved to be arrested. My concern is that this case has demonstrated that anyone who can cause a UK court order to be severed against this company can expose their users. It also makes them a target for hacking, social engineering, infiltration and other attacks which could gain access to these logs without a UK court order.
As a general rule, if information exists and people want it, there is a very good chance it will escape, if only by accident.
I founded this company, Anonymizer.com, and I personally stand behind our services. We have clear privacy policies, we keep no logs of the surfing activities of our users, we have no way of identifying what user may have visited what website. We have an unblemished record of providing robust privacy since 1995.
As I have said in many previous posts, it all comes down to trust. If you don't know who is providing the service, and don't have the ability to research their history and gauge their integrity, you should not use that service.