If you ask me, we should look to implement the (undocumented?) XP skinning API's -- with a deliberite sprinkling of internal extensions to clean up some of the messy parts if they are too slow for "built in" wine skins.
I think they are fairly well documented from looking at them a few months ago.
It's probably not /that/ difficult to figure out, especially if one is armed with something like WindowBlinds to hack on. After all, they figured it out at StarDock, (although they might have the "top secret" special sauce from MS for all I know...) and some of it is probably out there on the net.
WindowBlinds uses extensive hooking from what I recall - it made Windows (98) rather unstable. XP theming is different, it's actually built into the common controls library.
Once you have a skinning API, you just implement a 'gnome compat' and 'kde compat' skin (or even just an automagical one that does both) the thing would "just work", right? Why, it shouldn't take more than a couple of hours ;) (WARNING: that last part was a joke, if you set your watch by this you very well may miss work for several years).
I don't think we could do KDE skins, as (surprise) they depend on Qt which is GPLd. Most projects out there (mozilla, openoffice) use GTK theming engines.
Might be harder than some other approach to this problem, but IMO it would be a waste to expend labor building "skins" into wine using some other architecture which might be non-orthagonal to that used by MS operating systems.