Gotta look into pywallet - sounds very promising.
But want to clarify that It's not a problem finding the file itself when they are visible to the OS.
BTW: My guess is that the quickest way to find an intact wallet is to just use something like "dir \wallet.* /s" or "dir \?allet.* /s" after undeleting.
It doesn't search for a filename though as the file may have been partially rewritten. It looks for private key headers that you can find in a wallet.
It'd be easier to use on Linux as AFAIK nobody tried the key recovery function on Windows.
You can also use wxHexEditor (all platforms) that will basically do the same thing but it is specifically designed to search a set of bytes. It's less blackbox than pywallet.