How do I stop MacAppStore from showing updates for deleted apps?
Usually this is a problem with spotlight.

The simplest step is to shut down the mac, disconnect all external drives, and start up to make sure no extra volumes are mounted. The next step would be to rebuild the spotlight index.

Lastly, search in other user accounts to be sure another user didn't somehow install or copy that App into their home folder.