Check is your version of e2fsprogs (e.g.
e2fsck -V). There was apparently a bug prior to version 1.40.2 that could cause e2fsck (which is called by fsck for EXT2/EXT3 filesystems) to incorrectly report filesystem corruption of this type:
Fix a bug in e2fsck which caused it to incorrectly salvange directories when the last entry's rec_len is bogusly too big. This resulted in a nonsense filesystem corruption to be reported, and required a second run of e2fsck to fully fix up the directory.
The RHEL 4 servers that I have access to have version 1.35 on them, so this could be the real cause of your problem. It might be worth installing a newer version and running fsck again to be sure.
If that doesn't help, it may indeed be a filesystem problem. According to this thread, it appears that this can happen if you have a directory containing a very large number of files (millions or more). "Fixing" it with fsck will result in the inode being truncated, as you saw. In the case of a directory inode, truncation will cause the directory to "lose" files, and those orphaned files will end up in the filesystem's lost+found directory. They will be named after their inode number, not their original names, so although you'll still have the files, it may be difficult to tell them apart.