Go to "Vkontakte" to the address vk.com. To log on to your page type on the main page, email and password. Select "Messages". In case you need to restore the deleted correspondence with any particular user, turn to him with a request to copy the message history and send it to you. This is the easiest option, as people are unlikely to have deleted your correspondence.
If you accidentally delete a message and have not had time to update the page or leave the website, it will be easy. To do this, click on the words "Recover" which appears immediately after removal.
It is possible that you did not delete the message. Check it out. Remember the contents of the letter. Then go to "Messages" and type in the search on the right any word that contains the letter. Maybe you will find what you are looking for.
If you need to recover messages from different users, the method above will not work. Open your page and scroll it to the bottom. There you will find the line "Help". Select it.
Take a look at your email. If setting "Vkontakte" you didn't cancel the "Notify by email", then look for the right letters there. Of course, if you "clean" box, this way you will not do.
You will see a window, write your message for the employees of the technical customer support services. Tell us in the letter that you accidentally deleted the relevant correspondence, and ask about her recovery. You'll have help, if possible. Then don't forget to check your email Inbox, as there will come an answer from the support service of "Vkontakte" to your question. Just do not need to do this immediately after sending the message, because the members of this social network daily treat thousands of people.