A glance through ldap-3.3/servers/slapd/back-ldbm/add.c makes me think
that NEXTID should not be incremented in this case. The internal
li->li_nextid counter maintained by the LDBM back-end is decremented if
no other add operations have been initiated between starting an add and
finding out that the add can't succeed.
Are you by chance adding entries without waiting for the result(s) from
earlier add operations to come back? If so, that would explain the
behvaior you see. The good news is that extra incrementing of NEXTID is
not harmful. It is only essential that new entries by added with some
id that is higher than all previously added entries.
-Mark