Indexes and Timestamp Comparisons

I have a table called session:
                 Table "session"
 Attribute  |           Type           | Modifier
------------+--------------------------+----------
 sessionid  | character(32)            | not null
 usernumber | integer                  | not null
 timestamp  | timestamp with time zone | not null

I have two indices on this table: moo, a btree on timestamp, and
session_pkey, the implicit unique btree on sessionid.

I need to periodically eliminate timed-out entries from this table.
This is where my problem is. I created a test table that has a million
entries in it. I try to select the valid session ids and it uses an
index scan with moo; I try to select the invalid sessionids and it uses
a sequential scan which is considerably slower. I was also playing
around with some other timestamps to compare values and found that just
by changing the > to a < I would change whether it used a seq scan or an
index scan (it wasn't consistent though as to which scan it used for
which boolean.  Any suggestions on what I can do? I vacuum analyzed the
table right before I performed these explains:

This is a where for invalid sessionids. This is the one I actually need
to be able to run.
main=# explain delete from session where timestamp < '2001-08-27
12:26:03-05'::timestamp;
NOTICE:  QUERY PLAN:

Seq Scan on session  (cost=0.00..22815.21 rows=999257 width=6)

EXPLAIN
This is a where for valid sessionids.
main=# explain delete from session where timestamp > '2001-08-27
12:26:03-05'::timestamp;
NOTICE:  QUERY PLAN:

Index Scan using moo on session  (cost=0.00..3653.36 rows=1000 width=6)

EXPLAIN

These are a couple of random wheres. If it's of any consequence, this
timestamp is before all of the timestamps in the table.
main=# explain delete from session where timestamp < '2000-08-27
12:26:03-05'::timestamp;
NOTICE:  QUERY PLAN:

Index Scan using moo on session  (cost=0.00..3653.36 rows=1000 width=6)

EXPLAIN
main=# explain delete from session where timestamp > '2000-08-27
12:26:03-05'::timestamp;
NOTICE:  QUERY PLAN:

Seq Scan on session  (cost=0.00..22815.21 rows=999257 width=6)

EXPLAIN


Any help would be appreciated,

Josh Voils