German "dragnet investigations" and "pattern investigations" come to mind. The German BKA (the equivalent of the FBI) keeps a giant database that correlates "suspicious" behavior. [...]
If you collect enough points, the feds come by to interrogate you.
This is a gross exaggeration. "Pattern investigation" can be used to investigate certain severe crimes that cannot be solved otherwise. It must be warranted by a judge, naming the patterns that the respective committer is believed to match. There have been three "pattern investigations" ever, since the law was passed in 1991 (none of them successful).
It appears naive to claim that GAK could not happen under a Privacy Commissioner. It could and it will.
At least one German law professor argues that GAK is no problem if the escrow agents are regularly inspected by the Privacy Commissioner. The Privacy Commissioners on the other hand say that a crypto regulation would be unconstitutional. I agree that the existence of privacy officials will not prevent GAK. But the constitutional protection of privacy should. The German privacy regulation is based on a decision of the Constitutional Court which states that the citizen must be protected from an omniscient state, and from omniscient business. This decision clearly makes the scenario you described above illegal. The government draft of the Information and Communication Services Law specifies that service providers "shall make it possible for the user to use teleservices and to pay for them either anonymously or using a pseudonym, insofar as this is technically possible and can be reasonably expected". The Bundesrat (Upper House) disagrees: "Users [...] can also be information providers that e.g. post information to the Internet. If these have a legal claim to use the service anonymously, they will in future be able to commit crimes without having to fear to be identified." Others warn that failing to let the market decide will lead to misinvestments, and that anonymous services will quickly be deployed on a voluntary basis if there is a demand. It's probably obvious which of these are right. Nevertheless, I think it is encouraging that the government accepts that anonymity has a value. (They will never learn that sometimes it is better not to make a law.)