Shoutbox

You could go to:

Personal settings > Privacy

And click on every contact you deleted and select 'add to contacts'


Then you can do the steps mentioned above.

As far as i know, thats the only way possible you can do, what you're asking for.