So long story short:

I dropped the wrong app into 'clean my mac' and I hit 'cancel' but it was too late by that point.

I rebooted and appstore said it had an update, when I opened appstore it was showing an update for the app I just uninstalled.

I tried clicking 'update' but it gives me an error saying it's unable to install after 'downloading'.

When I try to go into 'purchased apps' it shows the app as uninstalled so I click 'install' and I get an error saying it's already installed.

I'm running Lion OS X, latest version, updated, mac book pro is only a few months old.

I tried searching through the entire system to remove all traces of the app, after rebooting appstore no longer shows the app and no longer shows the update but on the apps page it still says 'Update'.

I tried reinstalling the app from desktop OUT of the appstore and again says the app is 'already installed'.

So after reading more about lion I found an article that spoke about 'BundleID' being the thing that tells appstore what's installed and needing updating however I can't find the location of where the BundleID would be.

Any thoughts?

I've tried CCleaner, AppCleaner etc and none of them show the app, mainly because it is uninstalled.

Update

I've spoken to Apple Support who confirmed that there is a file in the system that connects separately to tell the system if there are updates available however they declined to inform me of any further details.

Apple also referred me from technical support to iTunes App Store opposed to Mac App Store support and from there I have been referred to AppleCare who are currently 'investigating' this issue.

Hopefully there will be a fix that's simple to implement for people having similar issues, this appears to be a more common issue than I previously thought.