Relationship between a recovery and a ROM
Is a different version of the Recovery really needed for different OS versions?


No. In case of updating custom ROMs you're completely right in that the recovery is mostly* independent of the ROM used.
However, phone manufacturers sometimes push out updates that change some vital parts of the phone. For example, repartition the phone. This is why sometimes you need a different recovery for the phone after major software updates.


  Is this something specific to ClockworkMod, or is it how Android's recovery system works always?


This is something that depends on the phone and the the manufacturer's customizations.


  If a recovery can be used to update the OS to a different version, does the recovery then become invalid after the update?


Factory ROMs are not always in the update.zip format, thus they're not always applied using the recovery. In these cases, the recovery is commonly among the parts that are updated. Furthermore recovery can be updated from the recovery just like the boot image (kernel.)