Autovacuum not keeping up. (PG 9.2.9)

Hi.

I have a large  database with a message queue table, that has high
activity. The database supports 1-300 client connection concurrently,
 having transactions open in up to 30 minutes each.

Recently I am seeing autuvacuum being issued, but it takes
ages to get through the message queue table, with strace showing waiting
for semop's for 10's to 100's of seconds.

There is no sign in pg_locks about this lock activity, so it is really hard
to digest down to the offending processes.

Currently autovacuum has been activly running for about 3 days on this
table, not finishing a single run.

I have seen this before and one option is to pull down everything, vacuum
full or cluster the tables and start up again. But I would really like to
get to a permanent solution here.

Autovacuum for other tables are going fine, so it seems to be related to
the high-activity of this table.

PG 9.2.9

Thanks.