Fire up Time Machine,
In the search box (top-right) of the TM finder window, type in the name of the file,
now manually go back in time, when you get to, or any time before the file was deleted, it will show up in the search window.
I just tested this, and it does work.