In XP files deleted to the recycle bin are renamed to Dcxx.ext, where xx is an ascending number. You could look for the file under that name, there's no need to run a deep scan. Or sort the path name and then look in c:\recycler.
NTFS clusters should be at least 4k, but the size of the file is irrelevant. Recuva will see, but has the sense not to recover, files of zero byte size.
There have been other reports of newly deleted files not being found. Whether this is due to the file record slot in the MFT being immediately overwritten by some other Windows process or not I don't know. In any event all deleted files are newly deleted at the start of their life (or should I say at the start of their limbo). I dunno, somebody should come up with a theory we can all bash.