This can happen if a registry key pertaining to the uninstalled patch was not correctly updated.
There you will see an entry for each hotfix or patch that has been installed.
Check the registry key pertaining to the Patch in question.
You will see a DWord value for "Installed" where 1 = installed and 0 = not installed.
If the value is set to 1, as shown below, change this to 0 and try the install again.
The Patch installation should now pass this check.