Tried Undo, it was greyed out... nothing in Deleted Items either.

I found OutlookFix and it actually found all the deleted items, but
they want US$139(!!!) for the version that will actually recover
them... little insane and WAY out of the budget.