You'd pretty much have to jump into your Steam folder, go into the "steamapps" directory, and delete any GCF/NCF corresponding to what you deleted. If the file is an NCF (i.e. most non-Valve games), you'll have to go into the "common" directory and delete the folder corresponding to the game. Make sure to go into the folder and back up and saved games that might happen to be there if you want to keep them.*
*Note: whether they are saved in there depends on the program. Some games, particularly older ones, put their saved game files into the program directory. Many newer ones chuck them somewhere in My Documents (which is REALLY FUCKING ANNOYING because (1) Vista/7 provide a very lovely "Saved Games" folder that nobody uses, not to mention that a lot of games designed for XP use the much neater "My Games" folder inside of My Documents and (2) I like to my DOCUMENTS in that folder. I can tolerate XP-era games putting their shit in a "My Games" folder, but there's no fucking reason why I should be seeing folders named "EA Games", "Bioware", "EVE", "Adobe" (not game-related, but still), "StepMania CVS", and "WBGames" in there -- and yes, on a fairly new Windows 7 install I already have six different pollutants in my Documents directory that I have to skip over every time I want to sort shit out...fucking assholes).