Ende des Jahres 2006 haben die regierenden Parteien mit sehr knapper Mehrheit des Gesetz zur Speicherung von Verbindungsdaten auf Vorrat (sog. Vorratsdatenspeicherung) beschlossen. Dieses Gesetz wurde maßgeblich von Innenminister Schäuble vorangetrieben und passierte sowohl Bundestag als auch Bundesrat. Sinngemäß werden sämtliche Verbindungsdaten aller deutschen Bürger erfasst und für einen Zeitraum von sechs Monaten gespeichert, um staatlichen Stellen in Straffällen Zugriff darauf zu gewehren. Begründet wird diese, die freiheitlichen Rechte jedes Bürgers beschneidende, Maßnahme mit dem latenten Schutz vor terroristischen Anschlägen.
Kritiker bemängeln die Begehrlichkeiten, die solch erfasste Daten wecken. Ähnlich wie bei den Mautbrücken, die bereits heute für völlig andere Zwecke als die, die damals Grundlage für die Entscheidung waren, genutzt werden, ist anzunehmen, dass sich weitere staatliche Stellen, etwa die Film- und Musikindustrie schnell via Lobbyarbeit oder politischem Druck Zugriff auf solcherlei erfasste Daten verschaffen. Für Anbieter von Telekommunikationsdiensten fallen außerdem hohe Kosten durch Erfassung und Speicherung der Daten an. Grundrechtlich ist die Maßnahme höchst bedenklich, da die persönliche Freiheit einerseits verständlicherweise der neuen Dimension des Terrors teilweise geopfert werden muss, andererseits ca. 80 Millionen Deutsche unter Generalverdacht gestellt werden. Gerne werden nicht ganz falsche Parallelen zu Stasi Zeiten in der DDR gezogen, die ebenfalls durch Überwachung der Bürger von sich Reden machten.
Dienste zum anonymen Surfen im Internet könnten aufgrund der neu beschlossenen Gesetze zur Vorratsdatenspeicherung an Relevanz gewinnen. Auch Anbieter solcher "Telekommunikations-" bzw. "Datendienste" sind im Rahmen des Gesetztes verpflichtet, Daten zu protokollieren und zu erheben. Es ist von einem Anstieg des Interesses an ausländischen und Offshore Anbietern auszugehen, die in liberaleren Ländern als Deutschland sitzen. Auch von einem Anstieg der Verschlüsselung und Anonymisierung von E-Mail Verkehr ist auszugehen. Als unbescholtener Bürger, aber sicher auch als Terrorist, kann man solcherlei Dienste nutzen, um die Effekte der Vorratsdatenspeicherung zu umgehen. Auf diesem Hintergrund stellt sich verschärft die Frage nach der Sinnhaftigkeit dieser bisher nie dagewesenden Maßnahme.
Aktuell wurde Ende des Jahres 2006 eine Verfassungsbeschwerde von über 25.000 unter Federführung von Rechtsanwalt Meinhard Starostik beim Bundesverfassungericht eingereicht. Auch ein Eilantrag zur Aussetzung der Vorratsdatenspeicherung hängt an. Die Entscheidung des Gerichtes bleibt trotz Zuversicht einiger FDP Politiker zweifelsohne abzuwarten, nachdem auch Bundespräsident Horst Köhler das Gesetz unterzeichnete. Weitere Informationen zu diesem Thema finden sich auch beim Arbeitskreis Vorratsdatenspeicherung (AK Vorrat).