Just curious. Have you checked that the tables are being vacuum/analyzed periodically and that the statistics are up to date? Try running the following query to verify:
A vacuum analyze runs every night and there would not have been many inserts or updates to the tables used by the lookup function since the latest vacuum analyze. I think I may have even done a vacuum analyze on the two largest tables after the first DB shutdown.
One thing to check (I ran into this two weeks ago) -- even though vacuums were happening, a query running on a standby machine was preventing the vacuum process from removing the dead rows. You may want to check for bloat or use 'vacuum verbose' to see if there's many dead rows not being cleaned up.
