In 4.0(3) you could not restore deleted items over the phone conversation - in 4.0(4) this feature was added - here's a link to the release notes for 4.0(4) that talks about that:
The only other way to do this if you don't have web inbox is to have an admin fish it out of the deleted items folder using a desktop client like Outlook for the user.
Learn, share, save
Discover and save your favorite ideas. Come back to expert answers, step-by-step guides, recent topics, and more.