Postgresql 7.4.8 inconsistent index usage

Hello,

I'm experiencing inconsistent usage of an index that I cannot explain.
This is in postgresql 7.4.8. Details are as follows:

I have a relatively large table (~3.5 million rows):

SCANS=# \d nessus_results;
Table "public.nessus_results"
Column | Type |
Modifiers
-------------+-----------------------+-----------------------------------------------------------------------
result_id | integer | not null default
nextval('public.nessus_results_result_id_seq'::text)
scan_id | integer | not null
ip | inet | not null
port | integer | not null
service | character varying(32) | not null
plugin_id | integer |
criticality | character varying(16) |
description | character varying |
Indexes:
"nessus_results_pkey" primary key, btree (result_id)
"nessus_results_scan_id" btree (scan_id)
"nessus_results_scan_id_criticality" btree (scan_id, ip, criticality)
"nessus_results_scan_id_result_id" btree (result_id, scan_id)
Foreign-key constraints:
"$1" FOREIGN KEY (scan_id) REFERENCES nessus_scans(scan_id)
"$2" FOREIGN KEY (ip) REFERENCES hosts(ip)

There are approximately 100 unique scan_ids in this table. The
following should not happen as far as I can tell:

SCANS=# explain select * from nessus_results where scan_id = 55;
QUERY PLAN
-------------------------------------------------------------------------
Seq Scan on nessus_results (cost=0.00..127170.34 rows=42640 width=169)
Filter: (scan_id = 55)
(2 rows)

SCANS=# explain select * from nessus_results where scan_id = 56;
QUERY PLAN
--------------------------------------------------------------------------------------------------------
Index Scan using nessus_results_scan_id on nessus_results
(cost=0.00..126632.83 rows=41813 width=169)
Index Cond: (scan_id = 56)
(2 rows)

SCANS=#

Both scan_ids (55, 56) exist. Yes, I've analyzed the table. I've
also tried upping the number of statistics to 100, with no apparent
change.

Thanks,
--Stephen