Personally I love Patchlink like I said above. It runs an agent on the desktop. Once the agent is installed (which can be pushed out automatically or manually run) it automatically detects the the Patchlink server. On the server you can setup groups of machines to delegate control over, setup baselines, etc. It supports all windows OS's, redhat, solaris, and will also do patches for office, citrix ICA clients, adobe, etc.
Patchlink can also help you create a custom package if you need to deploy it in your environment. But don't treat it like software deployment like SMS (even though it can begin to do it), it is patch management.
I don't remember costs though... sorry.