I've been using a trick since the ext2 days to reduce fsck times by a lot.. Reduce the inode count. I seem to recall EXT3 allocates 1 inode for every 16kb of diskspace by default. This means 20 million inodes on a 300gb partitian. 2.5gb scanned, on every fsck! A lot of the time, this is overkill. I generally run my parititians with 1/5 to 1/20 this number of inodes. I don't have any partitians formatted under the defaults to compare this to, but a mostly full 300gb partitian, with 1M inodes and 50k files, fsck's in under 10 minutes.

One reason Ext4 has faster fsck times because it tracks which inode groups are totally unused, and it avoids scanning them.