Nothing special about NSF. However, it is more likely to be able to recover a small file than it is to recover a large file, and mail files and mail archives tend to be large. That's probably why you couldn't recover it -- the files space was already re-allocated.
I would stop using the computer and only use programs that boot from USB flash drive or CD, since any additional writing to the disk may cause data to be totally lost.
Anyway look at Google these programs. There are many different. If you have no time to search, I can from experience recommend utility Lotus Notes Recovery Toolbox. I think it may come in handy in this situation. http://www.oemailrecovery.com/lotusnotes_recovery.html