FYI, I have fixed my issue.
I created a temporary login account (with admin access)
Signed into the App Store using the AppleID of the old user who was removed (fortunately I knew who this was and had their password)
Reinstalled the apps which were complaining.
Uninstalled these same apps using the 3rd party app AppCleaner (I believe AppZapper or similar would also work), and in addition to the main app file, a small config file was also detected and deleted for each.
Deleted the temporary account.
I searched through this thread and others, and my problem was never solved until I got this answer from Mac Support (Kimberly, who was extremely helpful):
1) Open the App Store application.
2) Click on the Store menu.
3) If you are not signed in to the App Store with your Apple ID, you will see a "Sign In…" option.
4) Click on the Purchased tab.
5) You should see a message "You Have 3 Apps to Accept". Click "Accept" next to the iLife apps (iPhoto/iMovie/Garageband).
If this does not work (which it didn't, in my case), proceed to these steps:
1) Perform a Spotlight search for the file "adoption.plist".
2) If you: Locate the file, drag it to the desktop. Do not locate the file, proceed to section 4.
3) Relaunch the Mac App Store. The Accept button should display in the Purchases section.
4) If the Accept button is still not displayed in the Purchases section of the Mac App Store after moving the adoption.plist file, drag an iLife '11 application from the Applications folder to Trash.
5) Once the application has been moved to Trash: Launch the Mac App Store. Search for the application that was moved to Trash. Click the application in the search results to view the product page for that application.
6) If the Accept button displays below the application icon, you will need to click the button. If successful, the applications are now accepted to your account.
I had a similar problem and tried the reindex Spotlight fix and this one: http://www.ngpixel.com/2011/06/25/mac-app-store-you-have-updates-available-for-t he-other-accounts-bug/ and tried the solution by commenter Renso on the same site. Nada.
My problem was that all the apps that would not update were not in the Applications folder. For some reason they were actually on another drive. It seems the App Store app scans all the drives and because the apps were not in their original location it produced this misleading error message.
This is such a poor error message—obviously a lazy programmer who couldn't be bothered specifying a real message pertinent to the actual problem.