How about running fsck only when the file system was not properly unmounted the last time it was online? (crash, power fail) Assuming the file system is robust and bug-free, this should be adequate.