Optimization disaster

At last I decided to post my problem here: I have a web application
running since one year on postgres 7.1.3 with good performance. Now
suddenly a query takes huge amounts of time: I tried to turn of
SEQ_SCAN, and it was fast again.

The following Query needs about 0,2 seconds with SEQ_SCAN set to OFF
and 150 seconds with SEQ_SCAN set to ON:

EXPLAIN
SELECT DISTINCT location_elem_id, locationseason_id, valid_from ,
valid_until, startday_exclude FROM bc_quicktravel
WHERE valid_until >= '2002-10-17' AND valid_from <= '2003-02-13' AND
attrib_id < 0
AND location_elem_id IN (SELECT elem_id FROM bc_catalog_x_elem
WHERE catalog_id IN
(186827,54786,186724,186829,73115,186831,186726,798429,186833,1368557,186728,186835,186837,186730,1821382,75083,297219,186732,63533,186781,75078,186736,902810,129859,1178799,186750,75281,1387815,54786,1368557,297219,1178799,936688,55706,132578,408097,132576,136852,160655,160657,160653,160665,73110,73115,1821382,1476580,1309559,1303367,1202899,1179539,1106603,1140768,950925,798429,902810,466934,334726,288050,197983,187203,186781,186783,186789,0,3011678,68214,54686,68414,68419)
AND active_from_time < '2002-10-16 23:59:59 +0200'
AND active_until_time > '2002-10-16 23:59:59 +0200'
AND elem_active_and_released = 't'
AND elem_type = 'location')
AND (package_elem_id <= 0
OR package_elem_id IN (SELECT elem_id FROM bc_catalog_x_elem
WHERE catalog_id IN
(186827,54786,186724,186829,73115,186831,186726,798429,186833,1368557,186728,186835,186837,186730,1821382,75083,297219,186732,63533,186781,75078,186736,902810,129859,1178799,186750,75281,1387815,54786,1368557,297219,1178799,936688,55706,132578,408097,132576,136852,160655,160657,160653,160665,73110,73115,1821382,1476580,1309559,1303367,1202899,1179539,1106603,1140768,950925,798429,902810,466934,334726,288050,197983,187203,186781,186783,186789,0,3011678,68214,54686,68414,68419)
AND active_from_time < '2002-10-16 23:59:59 +0200'
AND active_until_time > '2002-10-16 23:59:59 +0200'
AND elem_active_and_released = 't'
AND elem_type = 'travelpack')
)
AND valid_until > '2002-10-16 23:59:59 +0200'
AND package_elem_id < 0
ORDER BY location_elem_id, valid_from
;

(1) I get this with without SEQ_SCAN set to ON (150 sec):

Unique (cost=1946377.12..1946383.16 rows=48 width=35)
-> Sort (cost=1946377.12..1946377.12 rows=483 width=35)
-> Index Scan using quicktravel_inx011 on bc_quicktravel
(cost=0.00..1946355.60 rows=483 width=35)
SubPlan
-> Materialize (cost=520.03..520.03 rows=24 width=4)
-> Seq Scan on bc_catalog_x_elem
(cost=0.00..520.03 rows=24 width=4)
-> Seq Scan on bc_catalog_x_elem (cost=0.00..520.03
rows=455 width=4)

(2) I get this with without SEQ_SCAN set to OFF (0,2 sec):

Unique (cost=1677.70..1677.71 rows=1 width=36)
-> Sort (cost=1677.70..1677.70 rows=1 width=36)
-> Index Scan using quicktravel_inx011 on bc_quicktravel
(cost=0.00..1677.69 rows=1 width=36)
SubPlan
-> Materialize (cost=837.80..837.80 rows=25 width=4)
-> Index Scan using bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey on bc_catalog_x_elem
(cost=0.00..837.80 rows=25 width=4)
-> Materialize (cost=837.80..837.80 rows=371 width=4)
-> Index Scan using bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey on bc_catalog_x_elem
(cost=0.00..837.80 rows=371 width=4)

So the
-> Seq Scan on bc_catalog_x_elem (cost=0.00..520.03
rows=455 width=4)

in (1) seems to be wrong...

I do a VACUUM ANALYZE regularly.

What's wrong? I don't want to turn off SEQ_SCAN, because many other
queries will suffer.

Dietrich