Cannot detect deleted files on Truecrypt encrypted drive

System used: Windows XP SP3. Drive: C:\ - whole disk encrypted.
D:\ is using Vista (dual boot) but not encrypted.

Situation: both drives have 750 GB and both are almost full. They are also fragmented. Can't use Defrag now because they don't have 15% free space. And I believe the last time I used Defrag Windows lost some files or show me some strange message about a correction done to the filesystem.

Health: Both drives are fine according to HDTune Pro.

Question:

I have deleted some files (each one using almost 1 GB) on the C:\ drive. RAR extension.

However, even after using Recuva and several programs, they never detected those files (they were deleted using Shift + DEL). If I do the same on D:\ the files will be listed (I did this today and some were marked as in "excellent condition to be recovered".

What makes me think how much time do I have to wait for Recuva and all other programs to actually show those deleted files on C:\. Or perhaps Truecrypt is preventing them from ever being displayed?

I am not sure but I think Recuva/other programs showed files deleted on C:\ but a long time ago and not in a good condition to be recovered. I am talking about big files.

I need to recover a specific file that was accidentally removed but don't know how to do that since the file never shows on reports.