Yes, you can do this. After playing the Steam-installed version of Frozen Synapse (so that you have a registered account and email address), you can go to Mode7's website and use the form there to request a link to download and install a copy of Frozen Synapse independently of Steam.
Note also that the Steam-installed copy can be run without going through Steam. Just browse into the install directory and run the exe directly. (Don't use the desktop icon created by Steam, as that runs it via a steam:// URL instead of starting the exe directly.)
I have personally used both of these methods, having initially installed FS on my dual-boot laptop via Steam, set up an icon to run it in Windows 7 without starting Steam, and also run it under Ubuntu without Steam even being installed. I then requested a download link from Mode7, used it to download the OS X version, and installed that on my MacBook Pro to run without Steam.
I know of only one way that this can happen in windows, and has nothing to do with Steam other than their not-so-great decision to install all content into Program Files.
If you are on Windows 7 or Windows Vista, and you have UAC set to ON, then change it later to OFF, this can happen.
UAC does thing evil thing where if a program tries to write to a "protected" area like Program Files, EVEN IF YOU ARE ADMINISTRATOR, when you get a UAC prompt and give permission, it actually writes any files that would normally go into that directory into a "virtualized" directory somewhere else.
If you turn off UAC, that will no longer happen, and as an awesome bonus, it will no longer know about the files that it virtualized.
So in your case, if you had UAC on, installed a ton of games, then later got sick of UAC and turned it off, this would happen as you described.
See the second paragraph in "Features" in the article on User Account Control.
If you have done this and turn on UAC again, your content will come back, but be a TOTAL mess because if you've downloaded more stuff with UAC off, then that will be invisible when you turn UAC on, and vice versa.
this drove me a little crazy once before I realized what was happening.
i'm curious to know if this is your issue.
Best Answer
Yes, games linked to your Steam account can be installed / uninstalled at will.
There are some rare exceptions where a game has additional DRM that limits the number of times you can install - but this should always be noted on the game's store page (the first example I've found is Dead Space 2, check the wall of capitalised text carefully to see what I mean) and there is often a way to "reclaim" those installs before you uninstall the game. So check the Store page for each game before you uninstall if this is a concern.
When you want to reinstall:
On your game list, if you switch to the "All Games" view you will find all the games you have linked to your account. Those that are not currently installed will be greyed out, and from here you can select for them to be downloaded and installed.