I assume that it is the fact that rows update frequently which is the problem here? But why doesn't Postgres re-use any of the empty disk pages?
Can you install the contrib extension pg_freespacemap and use "select * from pg_freespace('table_name')" to see if PostgreSQL agrees that the space is re-usable?