Hello AnotherElk,
the situation, that an uninstalled App is still shown in the app list but with the notice that it is not installed for the current user, is caused by updates of this app which were installed before uninstalling the app.
The app and the message will disappear, if you uninstall all existing updates.
Uninstalling these updates should be possible in Settings - Apps
2 Likes