paths_cleanup.php not working?

To reproduce: 

1. rename all folders inside user-files, for example: rename userA, userB, userC to user1, user2, user3.

2. now run:

php paths_cleanup.php --deep --agressive --remove-hidden

3. notice it should end with something that says it cleaned up as much as it processed, in my case:

Processed 92126 records.
Cleaned 92125

4. Now run the same command again (see step 2).

Expected behavior:

Nothing to cleanup, since there should be nothing left in the database.

Actual behavior:
Observing the output notice how it checks all old, non-existing paths ("/user-files/userA/..." and "/user-files/userB/..." and "user-files/userC/...". This makes no sense, the paths do not exist in the filesystem (renamed in step 1) and should not exist in the database (removed in step 2).

5. The second run (still showing old paths) for me ended with: 

Processed 46001 records.
Cleaned 46000

6. Third run (still showing old paths): 

Processed 23001 records.
Cleaned 23000

7. It keeps cleaning half of the records, 4th run, still showing old paths

Processed 12000 records.
Cleaned 11999

8. 5th run (still showing old paths)

Processed 6000 records.
Cleaned 5999

9. 5th run (still showing old paths)

Processed 3000 records.
Cleaned 2999

10. 6th run (still showing old paths)

Processed 1000 records.
Cleaned 999

11. 7th run!

-------------------- START ----------------------
1. Checking /user-files ......OK
Processed 1 records.
Cleaned 0
-------------------- END ----------------------

I would expect to only need 1 run :).