Apparently the NCFs contain information about what is installed and indicate to Steam that the game is installed. With the content remaining and the NCFs gone, Steam will report the game as "Not Installed". Choosing to install downloads new NCFs and sees the existing content and will update as needed if what is there doesn't match what should be there.
This is also happening to folks on Windows systems, quite a few of them in fact. This may very well be an issue with the game itself.
(I can't play it on my ATI cards regardless :( )