Upgraded to Windows 10 or reinstalled another OS? It would wipe out your installed programs list in Windows. Seems like the most likely reason...personally I treat Windows Programs & Features (Add/Remove Programs???) and the Steam library as separate.
Either way, first suggestion would be to make sure your Steam folders are properly set in Settings -> Downloads. If that's fine, telling Steam to download a game would have it recognize "oh, I have that game!" and would turn into an integrity check.