Originally Posted by skorobki
Sorry to say but yes you are. That is why it is recommend that you only have handheld delete turned on for just that reason. Even if you had BES you would need to do a restore from a backup to get it.
If he was on a BES, I think he could have just used the "Recoved Deleted Items" feature (from within Outlook). No need for backups!