Personally, my and all people with smartphones i know in person, have their Contact lists setup to be 'Synced' -synchronised to their Google+ accounts. This means all their phone contacts are saved to their Google+ and so if lost or get a new phone, they can re-synchronise with google+ to get the contacts back.
As for messages, would reply same as posted above