The early packages could really mess up Windows - especially on non-English versions. Later on there were some really good ones around like XPize or Vize for XP and Vista respectively.

Theming Windows was something I always appreciated but that ended by the time I've got 7. Instead I've opted for making workflow bit more smoother with some additional programs like Launchpad and small GKrellM-like sidebar.