I've had Drive Rescue for a while, and it works when I test it (for immediately recovering shift deleted items.) Completely forgot I had it until you reminded me. I guess after this thread I won't forget :) It's free btw, and claims a lot of capability.

A suggested test is to put some files on a floppy, quick format it and then try to recover - the author claims his will work in this case better than others. You definitely want to familiarize yourself with this type of utility when you get it, so in your panicked state when you need it, you don't screw it up.