If after uninstalling a software their shortcut remains on the AppGrid it means that there's still a file associated with that software.
You have to delete it to make the remaining shortcut disappear, so open the file manager, search for the name of the software you uninstalled and delete it.
Once deleted, the invalid shortcut disappears immediately.
Note that if you have 2 types of the same software (for example both flat and snap version) make sure you delete only the file associated to the type of the uninstalled software. For example, I had to delete the file containing
snap to remove the invalid shortcut, if I had deleted the one containing flat I'd have deleted the valid one 
.