Structure groups and folders definitely need to have versioning. It's too easy to change something and then be unable to undo the change. The same applies to publications (especially given the amount of care needed with Content porter to avoid clobbering your publication metadata). Categories and keywords? These should definitely be versionable too.
I wonder what they original rationale was for not versioning these items. Maybe it just didn't fit in the scope. I can't think of a technical reason why it couldn't work.