I can't reproduce this either on Stein or Queens with devstack. Haven't tried with Ocata yet. This is what I tried:

Create new user in LDAP backend:

$ ldapadd -x -w nomoresecret -D cn=Manager,dc=openstack,dc=org \
>         -H ldap://localhost -c -f peter.ldif.in
adding new entry "cn=peter,ou=Users,dc=openstack,dc=org"
$ openstack --os-cloud=devstack-admin user list --domain Users
+------------------------------------------------------------------+-------+
| ID                                                               | Name  |
+------------------------------------------------------------------+-------+
| eb55ea06af4ba6f1b7b90f4746f5c2d3e570a44a23829e9b581fe32d482bf697 | demo  |
| fbbc3741707c62db5eed4242978f09089d341df01f827b8a795731a188f166cd | peter |
+------------------------------------------------------------------+-------+

Auth with the user so that an entry gets created in the user and nonlocal_user database:

$ openstack --os-cloud=ldap token issue
...

Delete the user from the LDAP backend:

$ ldapdelete -x -w nomoresecret -D cn=Manager,dc=openstack,dc=org \
>         -H ldap://localhost cn=peter,ou=Users,dc=openstack,dc=org

At this point from the API perspective the user is effectively gone:

$ openstack --os-cloud=devstack-admin user list --domain Users
+------------------------------------------------------------------+------+
| ID                                                               | Name |
+------------------------------------------------------------------+------+
| eb55ea06af4ba6f1b7b90f4746f5c2d3e570a44a23829e9b581fe32d482bf697 | demo |
+------------------------------------------------------------------+------+

Manually removed the user from the mysql database:

mysql> delete from user where id = 'fbbc3741707c62db5eed4242978f09089d341df01f827b8a795731a188f166cd';
Query OK, 1 row affected (0.01 sec)

mysql> select * from nonlocal_user;
Empty set (0.00 sec)

User list still seems okay:

$ openstack --os-cloud=devstack-admin user list --domain Users
+------------------------------------------------------------------+------+
| ID                                                               | Name |
+------------------------------------------------------------------+------+
| eb55ea06af4ba6f1b7b90f4746f5c2d3e570a44a23829e9b581fe32d482bf697 | demo |
+------------------------------------------------------------------+------+
$ sudo systemctl restart memcached
$ openstack --os-cloud=devstack-admin user list --domain Users
+------------------------------------------------------------------+------+
| ID                                                               | Name |
+------------------------------------------------------------------+------+
| eb55ea06af4ba6f1b7b90f4746f5c2d3e570a44a23829e9b581fe32d482bf697 | demo |
+------------------------------------------------------------------+------+

Two other comments:

First, in my opinion, manually editing the database table is not supportable. Keystone's behavior after doing that is naturally undefined.

Second, regarding this comment:

> Ultimately, I believe we have to cleanup the id_mappings table, however, I believe the invalid assumption at the line below is still worth discussion:
https://github.com/openstack/keystone/blob/stable/ocata/keystone/identity/mapping_backends/sql.py#L81

I don't think that code comment is invalid. The ID mapping is deterministically generated from the user ID from LDAP and the domain ID. If it's there, it means that if there was such a user with such an ID and domain, it would have that public ID. It doesn't mean the user is guaranteed to still exist in LDAP or the nonlocal_user table.