The ticket created as per comment https://pagure.io/389-ds-base/issue/49031#comment-441593

386ds v.1.3.6.5on CentOS7.3 compiled from sources, memeberOf plugin activated:

cn=MemberOf Plugin,cn=plugins,cn=config
...
nsslapd-pluginEnabled: on
memberofgroupattr: uniqueMember
memberofattr: memberOf
memberofautoaddoc: X-Misc

We don't have circular groups. And the particular group that was emptied/recreated is a simple one, without any nesting. But each user is a member of 20-30 other groups on the average.

After some research i think i have found out the exact situation when it happens. The person needs to be explicitly and implicitly a member of the same group. If that person is "touched" during any group membership change, the error will pop.

Here is an example:
cn=Utilisateurs Service Lambda,ou=Groupes Globaux,ou=Groupes,dc=example,dc=com
cn: Utilisateurs Service Lambda
objectClass: groupofuniquenames
objectClass: top
uniqueMember: cn=Management Team,ou=Administration,ou=Groupes,dc=example,dc=com
uniqueMember: uid=unfortunate_user,ou=personnel,ou=utilisateurs,dc=example,dc=com

cn=Management Team,ou=Administration,ou=Groupes,dc=example,dc=com
cn: Management Team
objectClass: groupofuniquenames
objectClass: top
uniqueMember: uid=unfortunate_user,ou=Personnel,ou=Utilisateurs,dc=example,dc=com
memberOf: cn=Utilisateurs Service Lambda,ou=Groupes Globaux,ou=Groupes,dc=example,dc=com

With this configuration each time we add (or delete?) the uid=unfortunate_user to a third group, the error message will pop:

/May/2017:14:06:57.552645685 +0200] - ERR - memberof-plugin - memberof_fix_memberof_callback: Weird, uid=unfortunate_user,ou=Personnel,ou=Utilisateurs,dc=example,dc=com is not in the cache

Maybe it happens because uid=unfortunate_user is evicted from ancestor cache first time due to the implicit group membership and second time because of the entry's explicit membership...

The tests are made on development server so if necessary, i can easily enable debug logging, recompile a modified memberOf plugin etc.