I had exactly this same problem today [Android Studio 2.3.3, Android 8.0 on the phone]
This is what I discovered. The app that I was trying to install was not shown in the android Application window [the one where you have them all]. But once I went in: Settings->Apps&Notifications->AppInfo I could see this screenshot where it was said that this app was “not installed for this user”:
At that point I entered the app->clicked on the three points in the top right corner->Uninstall for all the users
Now when I tried to run the project through Android Studio the error message disappeared and the app was correctly installed
Hope this helps, have a good day
Antonino