alt Hacker NewsSteam is really good about that kind of thing. Not quite the same, but I have a couple of games on my account that haven't been sold on the store for years, and I can still download them any time. I don't think there's any way for publishers to really remove a game that's already been purchased.
You're correct. It's part of the Steam Publisher Agreement that basically, you can't remove your game from users who have paid for it.
And if you push an update that deletes the files, Valve can, will, and has rolled back the update.
Of course, there's also situations where Valve has assisted in removing titles at developers request, but it was a situation Valve was involved in - Specifically, a game called "The Ship" had a Multiplayer version, and it was built on Source, but they could never quite get it to work correctly, even with Valve's help. Wouldn't sync.
Valve helped them remove the Multiplayer version. (but you still kept the single player.)