I'm sorry to report that there is not a recovery option for deleted contacts at this time. A user's current contact details are stored in an addressbook.xml file, which is found at C:\SmarterMail\Domains\[DOMAIN]\Users\[USER]. However, the entries are removed from that file when deleted from the server. If you happen to have an old copy of that file, it's possible that you could pull the necessary information, but I unfortunately don't have a better method to recommend.
I'll go ahead and change this thread from a Question to a Proposed Idea, so we can facilitate tracking on the request of adding recovery options for contacts and other collaboration items.