missing chunk number 0 for toast value

Our database seems to have been corrupted. It is a heavily used database,
and went several months without any type of vacuuming. When we finally
realized that it wasn't being vacuumed, we started the process, but the
process never successfully completed, and our database has never been the
same since.

The exact error that we receive now is as follows:

postgres(at)server:~> pg_dumpall -p 5433 > dbmail_dumpall_23092008.sql
*pg_dump: SQL command failed
pg_dump: Error message from server: ERROR: missing chunk number 0 for toast
value 554339
pg_dump: The command was: COPY public.dbmail_messageblks (messageblk_idnr,
physmessage_id, blocksize, is_header, messageblk) TO stdout;
pg_dumpall: pg_dump failed on database "dbmail", exiting*

We have tried using the -d option of the pg_dumpall so we could get a full
dump of the database, and just start over from that, but that fails as
well. We have also tried reindexing the table, but although the reindex
didn't fail, it didn't solve our problem either. Our next option is to do a
full vacuum, but we are reluctant to take our mail server down for that
long, especially when we do not know for sure that it will either succeed or
fix our problem. I have searched the forums, but was unable to find a
solution that we have not already tried. The solutions didn't appear to
help others who had this problem either.

Any suggestions?

Thanks,
BJ