We have a deleted file on a system which we want to restore, so we tried to use /sbin/debugfs. However doing lsdel in it's command prompt gives us:

We thought file could be overwritten already, but when we tried utility on one recently deleted file, especially for test purposes it also showed 0 deleted inodes found.

Maybe debugfs needs some pre-tuning before usage?

Any help appreciated.

No tuning possible. If you "grep ext3 /proc/mounts | grep -v bind | while read dev discard; do echo lsdel|/sbin/debugfs $dev; done" you're bound to find *some* residue, but since we're talking journalling FSes the results most likely won't be complete. If the deleted file wasn't backed up (shame!) then the time between deletion and disk freeze should be as short as possible to have a chance to carve it, but that chance gets slimmer each time the disk gets written to.

I get all zeros, seriously

It couldn't be, could it?

It couldn't be, could it?
Debugfs for sure doesn't see everything deleted, you'll need to carve files out. Tools include F/OSS ones like Foremost or Scalpel, Autopsy, Sleuthkit/CarvFS or PyFLAG (also see HELIX Live CD) or Photorec, and then there's always (the horror... the horror...) commercial SW like X-Ways, FTK or Encase (these don't run on GNU/Linux).

A quick Forensic Toolkit vs Foremost test with a "dd" image of a /var/tmp showed FTK coughing up aprox 70 JPEG files of which 75 percent was readable, while Foremost gave me a mix of TIF, .doc and PNG files weighing in at 10MB each (yeah right). OK, a rather unequal test, but it should illustrate each tool has it's own strenghts and weaknesses and there's no guarantee the carving results are actually usable...

I do hope you made a dd copy of the disk or partition when you found out the files were deleted.