Use of sequence rather than index scan for one text column on one instance of a database

Hello-

I've discovered that lookups on one column in one instance of my
database performs badly.

The table has columns 'email' and 'key', both of type 'character
varying(255)', and both with btree indices. The table has ~ 500k
rows, and no rows of either column are blank or null, and all values
are different.

\d users (abbreviated)
Table "public.users"
Column | Type
| Modifiers
----------------------+-----------------------------
+----------------------------------------------------
id | integer | not null
default nextval('users_id_seq'::regclass)
password | character varying(40) | not null
email | character varying(255) | not null
key | character varying(255) |
...
Indexes:
"users_pkey" PRIMARY KEY, btree (id)
"index_users_on_email" UNIQUE, btree (email)
"users_key_index" btree (key)
"xxx" btree (email)

On the main production database, a select looking at the email column
winds up scanning the whole table:

EXPLAIN ANALYZE SELECT * FROM users WHERE (users.email = 'example.com');
QUERY PLAN
---------------------------------------------------------------------------------------------------------
Seq Scan on users (cost=0.00..21097.90 rows=1 width=793) (actual
time=186.692..186.692 rows=0 loops=1)
Filter: ((email)::text = 'example.com'::text)
Total runtime: 186.735 ms
(3 rows)

... where on that same database selecting on the 'key' column uses the
index as expected:

EXPLAIN ANALYZE SELECT * FROM users WHERE (users.key = 'example.com');
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Index Scan using users_key_index on users (cost=0.00..6.38 rows=1
width=793) (actual time=0.021..0.021 rows=0 loops=1)
Index Cond: ((key)::text = 'example.com'::text)
Total runtime: 0.061 ms
(3 rows)

We're running postgresql 8.3 on solaris with 8G of RAM on a sun X4100
connected to a battery-backed sun disk shelf.

select version(); reports: PostgreSQL 8.3.3 64-bit on i386-pc-
solaris2.11, compiled by /opt/SUNWspro.40/SS11/bin/cc -Xa

We have test databases which are restored (pg_dump/pg_restore) backups
of this data, and on these the select on 'email' uses the index as
expected.

Dropping and re-adding that 'index_users_on_email' had no effect.

Spelunking through our logs we seem to have had this problem as far
back as I can practically go, so I can't look at any changes that
might be suspicious.

We did try adding a new column (cleverly named email2) and copying the
data (update users set email2=email) and adding the appropriate index
and the query performed quickly. So we can fix the immediate problem,
but I'd feel more comfortable understanding it.

Do folks on this list have suggestions for how to further diagnose this?

Thanks in advance,
-Bill Kirtley