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