I had a similar problem with excessive fsck times under FreeBSD because I had 100 million plus files on it (mostly small thumbnails). My server would be down for at least 2-3 hours after a crash, sifting through all of those files to find and correct errors. At the time my server was crashing because of a bug with FreeBSD's soft updates causing a panic (the *nix version of a blue screen of death) so those 2-3 hours of downtime each time started accumulating at an alarming rate.
I fixed that nasty boot delay by enabling journalling, which removes the need for a mandatory single-user mode fsck after a crash has caused file system damage. There may still be unwritten data and indirect corruption leading to some weird things happening at the application level, but the file system itself is intact, so the OS boots in seconds rather than hours.
I don't know if there's a similar solution available for Linux's journalling file systems.
