Have you confirmed that the App Inventory Version and the App Deployment version match, in some cases the Version of the App is listed as a number and the short version is what people look at, the versions need to match not the short versions, see the attached pics

Oh, I totally forgot about this post.
We figured it out after a while. It was as you said wrong version number. :)

Thank you for reply tho!
Could this be the same with something Chrome or Firefox? I recently set them up in patch mgmt and they showed up in Self Service, I installed them, they show installed, and then bam they're back showing as 'updates available' despite being the same versions as what's already installed.