URGENT! Server Down Need Advice... Why does fsck not work?

I'm encountering this error on reboot:

Checking root file system...fsck 1.40-WIP (14-Nov-2006)<br />
/lib/init/rw/rootdev contains a file system with errors. check forced.<br />
/lib/init/rw/rootdev:<br />
modes that were part of a corrupted orphan linked list found.<br />
/lib/init/rw/rootdev: UNEXPECTED INCONSISTENCY: RUN fsck MANUALLY.<br />
(i.e.. without -a or -p options)<br />
fsck died with exit status 4<br />
failed. (code 4).<br />
* An automatic file system check (fsck) of the root filesystem failed.<br />
A manual fsck must be performed. then the system restarted.<br />
The fsck should be performed in maintenance mode with the<br />
root filesystem mounted in read-only mode.<br />
* The root filesystem is currently mounted in read-only mode.<br />
A maintenance shell will now be started.<br />
After performing system maintenance, press CONTROL-D<br />
to terminate the maintenance shell and restart the system.

When fsck runs during boot-up it scans for 3 or 4 minutes before it finds the error and fails (it checks 59% of the drive before doing so). Yet when I run fsck manually from maintenance mode as instructed using this command:

fsck -sAV -t ext3 /dev/sda1 -r

or

fsck -sAV -t ext3 /lib/init/rw/rootdev -r

It instantly reports:

Checking all file systems.
[/sbin/fsck.ext3 (1) -- /] fsck.ext3 -r /dev/sda1
e2fsck 1.40-WIP (14-Nov-2006)
/dev/sda1: clean, 1054350/59572224 files, 13243893/119136024 blocks (check after next mount)

Basically, it reports no errors and ends almost immediately.

Yet, when I reboot the errors are still there.

What am I doing wrong here?