T-Mobile has admitted losing 17 million German customer records including names, addresses, phone numbers, dates of birth and email addresses.
The records of German customers were stolen in 2006 and included secret addresses of politicians, an ex-federal president, celebrities and others likely to be at risk from having their contact details released. No bank details were included in the stolen data.
The company said a storage device containing the files "is in the hands of unknown parties". T Mobile's parent, Deutsche Telekom, said it had no evidence that the records had been used since 2006.
Although the records had been offered for sale online, no one had bought them.
The company said it had made every effort to get the data back and has improved procedures to stop a similar theft happening again, Der Spiegel reports.
T-Mobile is already under investigation by German prosecutors for allegedly snooping on calls made by board directors, major shareholders and reporters.
Deutsche Telekom apologised for the loss and has set up a hotline to deal with worried customers. German regulators are investigating the incident. ®