Thousands of "unattached inode" entries freezing fsck

We have some CentOS systems with ext3 filesystems that (on occasion) experiences long power failures that are longer than the UPS can handle. We run an fsck on the file systems at every boot, and sometimes they will come back on after a power failure, and when fsck runs there are tens of thousands of "unattached inode" entries:

Inode ##### ref count is 1, should be 2. Fix? yes
Unattached inode ##### Connect to /lost+found? yes

Where ##### is a different number for each entry. (I've set fsck to answer 'yes' to all questions, hence the "yes"es for the two lines, but I have also tried setting it to answer "no" to all questions). The problem is that it will go through about 7000-8000 of these entries, and then freeze, like it's reached some kind of limit and doesn't want to process any more entries. At this point, someone has to reboot it and it goes to another 7000-8000 before it has to be rebooted again. I'm pretty certain that this is not a hard drive fault because this has happened across 20 different systems and 20 different hard drives.

Does anyone have any ideas:
a) what might be causing the problem, and how to get around it, and
b) what I can do to fix/avoid it without any human intervention? Possible change filesystems, or something else?

I don't want any of these unattached files as I am sure they are just temporary files, so I don't have a problem with just dumping them all. I just can't find a way to do that =/