Hallo Christian,
wie du selber schreibst, heißt der Befehl in Outlook "Gelöschte Elemente wiederherstellen" und nicht "Endgültig gelöschte Elemente wiederherstellen". Beim endgültigen Löschen werden diese Elemente aus der Outlook-Datendatei auch endgültig entfernt. Sie können auch nicht wieder über ein Recovery-Tool hergestellt werden, da es sich hier nicht um Einzel-Dateien handelt, deren ursprünglicher Speicherplatz auf der Festplatte ggf. noch nicht überschrieben wurde, sondern um 'Ausschnitte', die aus einer Datei (*.pst) entfernt wurden.
Falls du irgendwo noch eine frühere Sicherung der Outlook.pst hast, könntest du versuchen über die Importfunktion von Outlook 2010 aus dieser die dort gespeicherten Kontakte (ohne Doppelungen) zu importieren. Eventuell kannst du auf diesem Weg zumindest einen Teil der gelöschten Kontakte 'retten'.
Gruß
Kalle