VACUUM VERBOSE outputs, nonremovable "dead row versions cannot be removed yet"?
The oldest transactions are some minutes old and haven't modified
  anything on the table yet.


That's not sufficient. I think what is required to mark these rows as dead is that, when these transactions were started, there was no other transaction that had touched these rows (doing an UPDATE or DELETE on them).

Updating or deleting a row will keep the previous version of the row physically where it was, and set its xmax field to the TXID of the current transaction.
From the point of view of other transactions, this old version of the row is still visible if it is part of their snapshot. Each snapshot has an xmin and xmax to which the xmin and xmax of the row versions can be compared.
The point is that VACUUM must compare row versions against the combined visibility of all live snapshots, as opposed to simply checking if a row change is definitely committed. The latter is necessary but not sufficient to recycle the space used by the old version.

For example, here's a sequence of events such that VACUUM can't clean up dead rows even though the transaction that modified them has finished:


t0: Long running transaction TX1 starts  
t0+30mn: TX2 starts and sets itself in REPEATABLE READ mode.  
t0+35mn: TX1 finishes.  
t0+40mn: pg_stat_activity shows only the 10-mn old TX2  
t0+45mn: VACUUM runs but won't eliminate the old versions of the rows modified by TX1 (because TX2 might need them).