Glacial delete

Have a pretty simple table with about 420K rows:

                 Table "wx_grib_file"
   Attribute   |           Type           | Modifier
--------------+--------------------------+----------
  grib_file_id | oid                      | not null
  name         | character(40)            |
  parse_time   | timestamp with time zone |
Index: wx_grib_file_pkey

In psql, trying to delete a number of rows is extremely slow. Aggregates
(count, min, max, etc) run in a couple of seconds.  But a delete
using a range of grib_file_id or parse_time takes about a second
per row, which is painful for deletes of thousands of records.

Here are the results of an example vacuum done after the delete:

# vacuum verbose analyze wx_grib_file;
NOTICE:  --Relation wx_grib_file--
NOTICE:  Pages 5200: Changed 9, reaped 29, Empty 0, New 0; Tup 455033:
Vac 2500, Keep/VTL 0/0, Crash 0, UnUsed 0, MinLen 88, MaxLen 88;
Re-using: Free/Avail. Space 222204/222204; EndEmpty/Avail. Pages 0/29.
CPU 0.86s/0.29u sec.
NOTICE:  Index wx_grib_file_pkey: Pages 2448; Tuples 455033: Deleted
2500. CPU 0.39s/3.65u sec.
NOTICE:  Rel wx_grib_file: Pages: 5200 --> 5171; Tuple(s) moved: 2500.
CPU 0.03s/0.46u sec.
NOTICE:  Index wx_grib_file_pkey: Pages 2449; Tuples 455033: Deleted
2500. CPU 0.29s/3.31u sec.
NOTICE:  Analyzing...
VACUUM

Any suggestions on how to speed this up?

--
P. J. "Josh" Rovero                                 Sonalysts, Inc.
Email: rovero@sonalysts.com    www.sonalysts.com    215 Parkway North
Work: (860)326-3671 or 442-4355                     Waterford CT 06385
***********************************************************************