Table Clustering & Time Range Queries

I am running several servers with Postgres 8.3 that are used to house
location data from thousands of devices. Location updates are quite
frequent, so our tables rapidly become fairly large (often about 2GB per
day of growth). We've been using Postgres for close to 10 years now and
have been very happy until recent performance issues with larger data
sets.

Our primary location table is clustered by "reporttime" (bigint). Many
of the queries we need to perform are of the nature : "get me all
positions from a given device for yesterday". Similar queries are "get
me the most recent 10 positions from a given device".

These are pretty simple and straightforward queries that run
surprisingly quickly either on small tables or tables that have been
clustered by reporttime. If the tables are large and haven't been
actively clustered for a while, the simplest looking queries will take
close to a minute to execute.

Unfortunately, the clustering operation now takes far too long to run in
any reasonable maintenance window. On smaller datasets clustering will
take from 30 minutes to an hour and on our large datasets several hours
(gave up at our 4 hour maintenance window limit). Obviously I would
love to have Postgres support "online" clustering, however I need to
figure a way around this problem now or start planning the port to
another database server.

We have tried the "SELECT INTO ... ORDER BY REPORTTIME" trick instead or
running cluster, but since the tables are quite large that is still
taking too long (although quicker than clustering).

I have spent more time than I would like looking into clustering options
and other load balancing techniques. I was thinking that I'd like to
take one server set down for clustering, while failing over to the
secondary database set. The problem is I don't see an efficient or easy
way to then synchronize the sizable amount of updates that will have
occurred since the clustering started back to the now clustered primary
database without significantly affecting write performance. If it is
difficult to solve, porting to Oracle or *gasp* SQL Server will be an
easier solution.

I have spent a lot of time Googling, and so far no obvious solutions
jump to mind besides either hoping (or helping) online clustering become
a reality on Postgres, or to migrate to a different DB engine. I'd
really appreciate any thoughts or suggestions.

-Kevin