Vacuums taking forever :(

In my conf_pg, the autovacuum is on, so the DB should be (or I hope is
being) regularly vacuumed.

These are my settings:

work_mem = 20MB
temp_buffers = 4096
authentication_timeout = 10s
ssl = off
checkpoint_warning = 3600
random_page_cost = 1
autovacuum = on
autovacuum_vacuum_cost_delay = 20
vacuum_cost_delay = 20
autovacuum_naptime = 10
stats_start_collector = on
stats_row_level = on
autovacuum_vacuum_threshold = 75
autovacuum_analyze_threshold = 25
autovacuum_analyze_scale_factor = 0.02
autovacuum_vacuum_scale_factor = 0.01

The autovacuum was clearly not enough, so we also have a crontab that
vacuums the tables every hour. This is PG 8.2.9.

These cron jobs are taking over 35 minutes for a vacuum! What's the
use of a vacuum if it takes that long, and the DB performance is
tragic in the meantime?

I'd truly appreciate some thoughts from people with experience of
vacuum management of highly available online databases. About 10-20
million accesses for this one. Most are SELECTs. We have about 500,000
INSERTs and about 800,000 UPDATEs. Just 11 tables, of which only one
is like 10 million rows. Two are close to 500,000 rows, rest are
really small. It is this 10 million row thing that's the worry.

Thanks!