Do they still keep a database of all previous customers? If only 1% request a deletion it would leave a fairly small group of people who requested the deletion. Then via genetic markers you could probably match them back up fairly easily with the right data.
