T-Mobile has admitted losing 17 million German customer records, with the records being offered online by criminals.
The records included customer names, addresses, phone numbers, dates of birth and e-mail addresses.
The records were stolen in 2006, and included the secret addresses of politicians, an ex-federal president, celebrities and others likely to be at risk from having their contact details released.
The bank says no bank details were included in the stolen data. T-Mobile, owned by Deutsche Telekom, says the customer records are held on a storage device held by "unknown parties".
It says the records have been offered for sale but it believes no one has bought them. It believes the records have not been used for ill-gotten gain since their loss in 2006.
German magazine Der Speigel revealed the loss.
