I stumbled across this cool service offered by Zyb, it offers to store contacts, events and messages from your phone for free. This is one of the service I have been waiting for some time since I lost my cellphone with contact information that I never had backed up anywhere. I wasted quite a lot of time trying to get all the contact information again. I tried to sync my Nokia N70m and it was done in a jiffy.
I hope i could have found this service before losing my cellphone.