A 'deeper' PostgreSQL autovacuum
You have a couple options. The basic thing is that dead tuples in the middle of the table, as you have guessed are not reclaimed for the filesystem with autovacuum.  Rather they are marked as free so that future inserts in the same table can use that space.  The space isn't bloated permanently.  It is available for re-use within the same table regarding future inserts or updates.

If you want to reclaim that space for the filesystem you have two options:

1)  vacuum full.  This locks things.  It is usually not ideal but sometimes it is the best option.  Also it takes a while.

2)  cluster on an index.  This rewrites the table into a new file.  It requires a lot more disk space, but is also a lot faster.  It does fully return free space back to the filesystem at the end however.

Both these require table locks.  They are not concurrent safe.  You don't want autovacuum deciding that now is a good time to lock tables for you so this is just the way it is.

Edit:  This wasn't obvious from the question initially but from the comment reply it looks like the problem here is that the free space map settings may be insufficient.  These settings were removed in 9.1 iirc but basically set the size of the free space map per table.  What happens in this case is that the free space map is insufficient to hold all dead tuples.  In this case tuples get deleted but the space can't be re-used.

When this happens bloat is the result and vacuum full or cluster can be necessary to recover space.  As an intermediate solution barring these, you can significantly increase your free space map settings and re-run vacuum (regular, not full) to update the fsm.  This won't recover space, but it will make more of the space available for re-use.