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