BTW, is there anything in Sync issues folder that might give you a clue?
Get MFCMAPI from mfcmapi.codeplex.com
Run it, choose session, logon (and select the profile if asked)
double click on the imap data file name
expand the root on the left to find IPM_SUBTREE. Expand it
Select the deleted folder for your account.
Nose around on the right click menu - If the Advanced> Restored deleted folder is active, click it. Other tables has a deleted option - not sure if it will be useful.