How to manage version control for patched contrib modules?
Use Drush Make. It's built into Drush 5. Your makefile will serve as not only documentation of what patches you're using, but documentation of what versions of everything you're using, where to download external libraries, it's practically guaranteed to be up to date, and it means you no longer have to store contrib and external code in your source code repository. Just your custom code.

Basically, you create a file that tells Drush Make what version of core to download, which contrib modules and themes to download, which external libraries to download, where to place them (you can separate contrib modules to a "contrib" subdirectory, for instance), which patches to apply (to all of those).

Drush Makefiles are used to build Drupal distributions.

Have a look at a pretty simple makefile from Discursive, and a more terse makefile from OpenOutreach.

EDIT: I really should include a link to at least one makefile that uses a bunch of patches and a much better example of using Drush Make on a client project: WiseDecider (check the makefiles in that install profile directory, then also go up a directory to find the rebuild.sh script that "builds" it -- downloads, patches, etc. the site and sets up symlinks and such to glue everything together. Also a disclosure: Wise Decider is a client of the Drupal shop I work for and Discursive is the open-source version of another client project of ours.

EDIT 2: Don't use any kind of "automatic updates" with this method. The process is:


Update your makefile locally
Rebuild the site by rerunning the build script
Test on your local instance of the site against a new dump of the production database (don't forget drush updb)
Deploy the updated codebase to your testing/staging server (don't forget drush updb) for internal QA / client QA (if applicable)
Redeploy the updated codebase to production (and again, don't forget to run the db update scripts).


Our deployment scripts (included in Wise Decider) use rsync and symlinks to pushing code to the remote LAMP server.