Alvaro, Scott - thanks for your replies and the direction you pointed me
into.
The underlying problem was that the cost limit was too low, so the
autovacuum process would run forever and not be able to do anything. I
reduced the cost delay and increased the cost limit form the default of
200 to 10000, which is slightly more than the longest time I saw when
running manually. Autovacuum now works as expected - the tables, which
have a very high rate of updates and some inserts (very few) are not
growing anymore. The run time for the scheduled background processes
(which perform some background aggregation) have gone down slightly
(about 10%) as well. Since autovacuum will prevent a deadlock, it is
definitely preferable to me over manually vacuuming.
Once again, thanks!