Time Machine : Can't find deleted files in Time machine
Can you see the files if you just browse the backup volume directly in /Volumes/?

If a file is deleted, it won't be included in new snapshots, but there will probably still be older snapshots that have it.

The folders for backups only contain files that have changed. Other files and folders are just hard links. If a file has been modified after the last snapshot, the whole file is copied instead of storing a delta. See the Wikipedia article for more information.