This error usually comes up when you install and uninstall an App more than once on SharePoint 2013. There are some solutions online that relates to SharePoint Online and updating manifest files when developing your OWN apps.
In our case this was a 3rd party app which caused the issue. The only solution provided by the vendor was to reinstall the app on a different site collection.
After some digging we found the solution below. It does require updating the SharePoint database via SQL (which is not allowed by MS), but then again how else do you fix it? <sarcasm>Run the Fix It Tool?</sarcasm>
Run this query on your content database:
SELECT [PackageFingerprint]
,[ProductId]
,[Package]
,[Title]
,[IsDownloadInvalidated]
,[SiteId]
FROM [AppPackages]
Identify the relevant app and site then run
exec proc_App_InvalidatePackage
@PackageFingerprint, @SiteId
This will invalidate your app
Then run
exec proc_App_DeleteInvalidatedDownloadApp
@PackageFingerprint, @SiteId
and BAM, the app is gone. Reinstall!