Users not fully deleting from the database
It definitely does sound like a missing foreign key constraint issue.
The Craft 2 version of the Fix FKs plugin for Craft 3 still lives here: https://github.com/pixelandtonic/craft-fixfks
I'd give that a whirl.