Gitlab: no user or key was provided : caused by keys not being removed from git own authorized_keys file

I was able to debug and uncovered the bug that is causing the infamous Gitlab: no user or key was provided errors message for users that do have the right keys.

This seems to happen if the key was previously registered as a deploy key (maybe even by another user) and removed after and re added to the the current account.

I was able to stop the key inside the authorized-keys file but with a key number (key-123) that does not exists inside the database.

The workaround seems to be to manually clean the authorized_keys file but that's not the point, as this problem is causing serious issues with automation.