The disk - containing customers' names and addresses with the account details - went missing on 29 May 2008.
The customers affected signed up to Virgin Media services in Carphone Warehouse stores from January this year.
It is not known why the data was burned onto a CD.
Virgin Media says it is working with the Information Commissioner's Office on the data breach. The company said it is in the process of contacting the customers affected.
Earlier this week, it was reported that the Scottish Ambulance Service had lost the details of almost 900,000 emergency calls on a disk that was in transit. That information was encrypted however.
Read more about data breaches: