1) First go to Run and type regedit

2) Go to:\HKEY_LOCAL_MACHINE\SOFTWARE\MICROSOFT\EXCHANGE\CLIENT\OPTIONS registry key.

3) Right click options and add new DWORD VALUE (data type is REG_DWORD) and then right click and rename to DumpsterAlwaysOn. It is case sensitive.

4) Then right click and modify and make the value 1 to turn the Recover Deleted Items menu choice on for all folders or enter 0 to turn it off.

5) Then go to Outlook , choose "Recover deleted items" option from the Tools Menu to get back your "permanently deleted" mails!

Note : This procedure can recover mails which were deleted by pressing shift+del in the past 30 days. I Tried and its working....

Thanks to my friend Vish for sharing this through an email.