And if possible also check if there is a beta/orevennewer version of the app.
I often flash new rom or restore and I have to use a backup application to restore apps and other things(The best I know about is Titanium Backup Pro, support the dev!) and most of the apps never appear in playstore's my apps list (even after using Titanium's market doctor feature) but when I search for the app play store shows I have the app installed and even that the app needs an update!
There are some Third Party markets but they often dont have the latest version and may possibly be infected with malware
So how to check for updates?