This may or may not be the same issue Tomas Vondra reported recently; see
https://www.postgresql.org/message-id/94f58897-861b-accf-a9f1-af4be816c0d3@2ndquadrant.com
where he posted a patch to fix the problem. Would you test that and see
if it solves the problem for you?
I've performed tests with and without patch provided by Tomas Vondra applied.
Conclusions:
1. Patch fixed issue with adding n_dead_tup value to reltuples.
2. Even without dead_tuples in a table, vacuum without analyze would bring reltuples value to inconsistent state.
3. reltuples value increases with absolutely every lazy vacuum iteration.
4. Existence of dead tuples would just increase inaccuracy of reltuples because of higher vacuum operations rate (depends on autovacuum_naptime value) and higher iteration increment of reltuples overvaluing.
5. Bug is pretty critical, especially with big tables with high modification rate.
Now it has been tested on 9.6.2, 9.6.3 and 9.6.5.
Please find postgresql96-vacuum-reltuples-fix-v2-tests.txt with performed tests attached.