BUG #3606: Query Plan Failure or Index Corruption?

The following bug has been logged online:

Bug reference: 3606
Logged by: David Tulloss
Email address: dtulloss@computersoftwareinc.com
PostgreSQL version: 8.2
Operating system: Windows
Description: Query Plan Failure or Index Corruption?
Details:

I have a very complex view that is starting to fail due to out of memory
error. When I run explain on the select that fails, the extimated cost is in
the TRILLIONS. When I dump and restore the db, it is back to normal
(estiamted cost in the thousands), but within a few hours of normal use (db
has been running for months) these queries begin to fail and the cost is
back up in the stratosphere.

I am operating under the assumption that we have an index corruption because
things work upon restore and then degrade under usage.

Vacuum Analyze instantly blows up the query planning on a newly restored
db.

This database is frequently written and read from all the time.

I've adjusted various environmental variables such as random_page_cost, etc.
But have only seen minor improvements (est. costs in the BILLIONS vs.
TRILLIONS).

HELP?!!?