I've often thought about this one too. I've seen implentations that used most of the tricks described in Greenspun's article, and also some that treated a database like CVS. Allaire Spectra serialized all data objects into XML blobs when storing them in the database, which made versioning easier but was not very efficient. Interwoven TeamSite collects all of your data in XML and then publishes it to the database using an XML-to-RDBMS bridge, but that means duplicating your data structure definitions and is basically a kludge. Most people end up just giving up on the idea of real versioning and using some kind of assembly stage instead, i.e. assemble everything on an internal content server and then periodically publish it all to the live server, like making a release from CVS.

For most content management problems like this, I think the multi-part key (id + version #) is the best way to go. You just keep a VERSIONS table which stores the current version number for each versioned table. You can even make this work for relationship tables if you choose a side that the relationship is from, e.g. you link foo (version 19) to bar (latest). If you put version numbers on both sides of the link and then one of the objects gets reverted, you can't easilly resolve it.

In order to make this easier to deal with from a progrmming perspective, I would suggest wrapping a database view around it. Then you can have simple keys in your queries and the view will join against the VERSIONS table and show the right one.