When trying to deploy my app to the Android device I am getting the following error:

Deployment failed because of an internal error: Failure [INSTALL_FAILED_UPDATE_INCOMPATIBLE]

I am aware of this question but the app is not installed. It has been removed/partially removed by Visual Studio during the attempt to deploy.

In the past I solved this by downloading the app from the google play store and then removing it from settings->Application manager. However, now i am getting the error "incompatible update" when it is trying to install it.

I tried to remove it using Titanium Backup and few other things but no luck.

EDIT 1

I realised (from @Motz) that I haven't mentioned that the obvious solution doesn't work. Namely, the app doesn't appear in Settings->Apps