Slow Vacuum was: vacuum output question

To follow up on an old thread that I started - I had a customer who
had a system where manual vacuum runs were taking a very long time to
run. I was seeing output like this:

INFO: "cpe": found 95498 removable, 18757 nonremovable row versions
in 11117 pages
DETAIL: 0 dead row versions cannot be removed yet.
There were 280173 unused item pointers.
0 pages are entirely empty.
CPU 5.35s/0.99u sec elapsed 724.38 sec.

Then, running vacuum again immediately afterword, on a system that was
basically idle, would result in nearly the same amount of time to
vacuum the table.

Getting a copy of the database from the customer, and loading it onto
my Postgres System and running the vacuum would result in runs that
took less than a second (as expected).

General opinion was that it was a disk-io problem. We rebooted the
system, and magically, the problem went away.

As tends to be the case with "magically" fixed problems, this one is
back. Now I have a different customer running Postgres 8.1 on Fedora
Core 6, and their system produced that log snippit above.

hdparm shows disk-io thruput being perfectly normal on their system.
Everything else on the system seems to be working correctly. The
reboot solution doesn't help. Vacuum still runs painfully slow.

I'm still waiting for a copy of their postgresql config file, but I'm
guessing that almost everything was left on the default settings.

I don't suppose anyone knows of any bugs that existed between postgres
8.1 and older linux kernels that led to behavior like this? I can't
really just ask them to upgrade their OS and/or Postgres on the hunch
that the problem should go away.... And I haven't yet been able to
reproduce anything like this on a system that I have control over.

Thanks for any ideas.

Dan