I just tried to start up the game and the Steam thing downloaded a patch. Since then, when i click on the play button i receive the error message:

Fallout:New Vegas does not appear to be installed and the installer cannot be found.
Try exploring your dvd-rom drive and selecting setup.exe to install game.

Unfortunately, that doesnt work either. It gives me the option to reinstall. Steam then validates it and says it is 100 percent verified.

The same thing has happened to me. I downloaded the patch, tried to launch it from steam, says I don't have the files on the computer even though I was just playing the damn game 10 minutes ago. This is getting ridiculous.

EDIT:

The patch doesn't seem to download all the way from steam. It suspends the download about 20 mb before the entirety is downloaded. When I try to resume, it doesn't do anything and eventually just says all files have been downloaded. Steam is a serious turd

try to delete *.ini files in "USERNAME\Documents\My Games\FalloutNV" folder...
...then start the game again from steam\game library list

This did not work. I've tried re-installing and the patch does not 100% download. Steam automatically suspends the download 20 mb before completion and whenever I attempt to resume the download, it miraculously says all files have finished downloading. Trying to start the game nets the same error.

No one else has this problem? Every time I reinstall, the patch does not fully download.

A lot of times with steam it downloads compressed or encrypted files and puts the decompression/decryption time in the percent value. It can't calculate the value correctly, which is why it stops and is suddenly done. I will agree, Steam is a turd, crashing and freezing all the time, but we aren't paying a monthly fee for it.