The data loss worried those switching to cloud computing
Microsoft says it has now recovered the personal data lost when its Sidekick servers suffered an outage on 13 October.
The online service backs up contacts, photos, calendar appointments and other personal data stored on the mobile phones of Sidekick T Mobile customers.
Microsoft Corporate Vice President Roz Ho says that all data will be restored, beginning with personal contacts.
She believes that only a minority of Sidekick users are still affected.
"The outage was caused by a system failure that created data loss in the core database and the back up," she wrote in an open letter to customers.
The number of customers affected was not released, but Sidekick is believed to have more than one million subscribers overall.
Microsoft says it has installed a "more resilient back-up process" to safeguard against a repeat incident.
The issue has been seen by industry experts as the largest failing for cloud computing in recent memory.
"This is the most spectacular loss of data on the web to date," Harry McCracken, editor of Technologizer.com told BBC News at the time.