When fsck is run on a well-trashed partition that has a large number of files/directories (for example a mail server using Maildirs, a news server, large office file server), there seems to be some internal limit on the number of directories and/or files that fsck can create within lost+found.  This results in many possibly recoverable files being deleted.

Fix: 

I don't really have any C skills, but on a box where I'm attempting recovery off of a dd image of a trashed fs, I've modified "dir.c" like so to make fsck just exit when it can no longer add files to lost+found:

if (makeentry(lfdir, orphan, (name ? name : tempname)) == 0) {
                pfatal("SORRY. NO SPACE IN lost+found DIRECTORY");
                printf("exiting...\n\n");
                exit (99);
                return (0);
        }

I then mount the fs r/w, copy off everything in lost+found, rm -rf lost+found, unmount, and then run fsck again.  I keep doing this until it's finished.  

I imagine someone more familiar with fsck could have it do something else at that point; like create a "lost+found1" directory and keep incrementing.  That's my best guess as to how to approach this.

Thanks,

Charles
How-To-Repeat: Trash a filesystem badly. :)  Then run fsck on it.  At some point, fsck will start spitting out the error "SORRY. NO SPACE IN lost+found DIRECTORY".  Since one is probably running with "-y" due to the large number of prompts a bad fs will have, from that point on everything fsck tries to "reconnect" into lost+found gets trashed.  You have lost possibly good data at that point.