When the index is modified during a callback from a search, the search list being returned is not stable and can therefore miss entries. The one-level index is a good example under subtree_rename, as entries are removed from the list as the search progresses.
Created attachment 14217 [details] a possible patch
Posted with tests to the list here: https://lists.samba.org/archive/samba-technical/2018-May/128185.html
Fixed in master with d02cd236dcbd8a44ecc85d1f7e95a48c95c0a479 for Samba 4.9 and ldb 1.4.0 Fixed in v4-8-test with 5c1d9b0b9acd5f4a1d2030f23829183cbbeb072d for Samba 4.8.3 and ldb.1.3.4. A backport to 4.7 and below is possible.