VACUUMs take twice as long across all nodes

Hullo, here's one of those dreadful touchy-feely hand-waving problems.
Our 5-node 8.1.3 Slony system has just started taking /much/ longer to
VACUUM ANALYZE..

The data set has not increased more than usual (nightly backups stand
at 1.3GB, growing by 10MB per day), and no configuration has changed on
the machines.

Nodes 2 and 3 take only the tables necessary to run our search (10 out
of the full 130) and are much lighter (only 7GB on disk cf. 30GB for
the full master) , yet the nightly VACUUM FULL has jumped from 2 hours
to 4 in the space of one day!

Like I say, no config changes, no reboots / postmaster restarts, no extra processes, and every machine has a comfortable overhead of free page slots + relations.

From a few days ago:
2006-10-20 03:04:29 UTC INFO: "Allocation": found 786856 removable, 4933448 nonremovable row versions in 53461 pages
2006-10-20 03:04:29 UTC DETAIL: 0 dead row versions cannot be removed yet.
2006-10-20 03:07:32 UTC INFO: index "allocation_pkey" now contains 4933448 row versions in 93918 pages
2006-10-20 03:07:32 UTC DETAIL: 786856 index row versions were removed.
2006-10-20 03:14:21 UTC INFO: index "ix_date" now contains 4933448 row versions in 74455 pages
2006-10-20 03:14:21 UTC DETAIL: 786856 index row versions were removed.
2006-10-20 03:22:32 UTC INFO: index "ix_dateprice" now contains 4933448 row versions in 81313 pages
2006-10-20 03:22:32 UTC DETAIL: 786856 index row versions were removed.
2006-10-20 03:24:41 UTC INFO: index "ix_dateroom" now contains 4933448 row versions in 44610 pages
2006-10-20 03:24:41 UTC DETAIL: 786856 index row versions were removed.
2006-10-20 03:27:52 UTC INFO: index "ix_room" now contains 4933448 row versions in 35415 pages
2006-10-20 03:27:52 UTC DETAIL: 786856 index row versions were removed.
2006-10-20 03:31:43 UTC INFO: "Allocation": moved 348324 row versions, truncated 53461 to 46107 pages
2006-10-20 03:31:43 UTC DETAIL: CPU 4.72s/17.63u sec elapsed 230.81 sec.

From last night:
2006-10-26 01:00:30 UTC INFO: vacuuming "public.Allocation"
2006-10-26 01:00:36 UTC INFO: "Allocation": found 774057 removable, 4979938 nonremovable row versions in 53777 pages
2006-10-26 01:00:36 UTC DETAIL: 0 dead row versions cannot be removed yet.
2006-10-26 01:06:18 UTC INFO: index "allocation_pkey" now contains 4979938 row versions in 100800 pages
2006-10-26 01:06:18 UTC DETAIL: 774057 index row versions were removed.
2006-10-26 01:19:22 UTC INFO: index "ix_date" now contains 4979938 row versions in 81630 pages
2006-10-26 01:19:22 UTC DETAIL: 774057 index row versions were removed.
2006-10-26 01:35:17 UTC INFO: index "ix_dateprice" now contains 4979938 row versions in 87750 pages
2006-10-26 01:35:17 UTC DETAIL: 774057 index row versions were removed.
2006-10-26 01:41:27 UTC INFO: index "ix_dateroom" now contains 4979938 row versions in 46320 pages
2006-10-26 01:41:27 UTC DETAIL: 774057 index row versions were removed.
2006-10-26 01:48:18 UTC INFO: index "ix_room" now contains 4979938 row versions in 36513 pages
2006-10-26 01:48:18 UTC DETAIL: 774057 index row versions were removed.
2006-10-26 01:56:35 UTC INFO: "Allocation": moved 322744 row versions, truncated 53777 to 46542 pages
2006-10-26 01:56:35 UTC DETAIL: CPU 4.21s/15.90u sec elapsed 496.30 sec.

As you can see, the amount of system + user time for these runs are comparable, but the amount of real time has more than doubled.

This isn't even a case for making the cost-based delay vacuum more aggressive because I already have vacuum_cost_delay = 0 on all machines to make the vacuum run as quickly as possible.

Any ideas warmly received! :)

Cheers,
Gavin.