Is there a way to restore deleted contacts via OWA?

OK, figured it out.

If this happens to you, chances are it is probably what my user was experiencing and what I had to decipher.

The picture in the OP is as accurate as OWA can get it, but it isn't "true". The actual contact wasn't deleted at all (confused yet by the pic? me too)...but instead it exists in the Conflicts folder under Sync Issues. In the case of my user, he had 3 different Sync Issues folders.

Looking in the Conflicts folder(s) I found multiple contacts from the past 6 months.

WHY?

It would appear to be a known syncing issue between Outlook/Exchange and Outlook 2011 for Mac. Further complicating it, the user has an iPhone syncing email, plus 2 other Macs that also have Outlook 2011 installed and syncing.

So, I restored the latest conflict contact for the user. There isn't a great way to prevent this type of syncing issue, short of limiting the user to a single email client.

However, this does at least explain why the OWA interface looked messed up and where the contact truly did exist, which wasn't where OWA was showing it to exist.

FOR REFERENCE INFO:

Conflicts Contains all the multiple copies of conflicting items in your mailbox. An InfoBar at the top of the original item advises you that a conflict for this item exists. The conflicting item is stored in the Conflicts folder. Clicking the InfoBar will bring up a list of conflicting items and allow you to resolve the conflict by determining which item you want to keep.

If you have made changes to an item, but are not seeing the updated item in your Navigation Pane folders, check for an InfoBar notice at the top of the item. If you cannot find the original item, check the Conflicts folder. It is possible that your changes caused a conflict with the original item, and the changes will exist in the Conflicts folder. - http://office.microsoft.com/en-us/outlook-help/synchronization-error-folders-HP010102440.aspx

The other option which you may have tried is to Right Click Deleted Items and select Recover Deleted Items. It will bring up all deleted items and then you click on the contact, or contacts, and select Recover. I just tried that as a test and the Contact I deleted shows up there. I then selected Recover and it allows me to select the folder (Contacts, Calendar, Mail, etc.) where I want it to be recovered to. Have you tried that?