You guessed exactly, without knowing. Chromes are Mozilla-style skins, which use the Mozilla GFX widget library. They are made using XCF, which is an XML-based standard for defining user interfaces (?) but the real problem is it means you have to have a billion instances of the rendering engine for all the widgets. The only part of Mozilla you want is Gecko, and once it's reusable, you should need no more than a "gecko.h" to build K-Meleon. So, the way to do this is exactly what you said, build it from scratch with nothing but the Platform SDK. Then you can also remove the toolbar backgrounds and that stuff.
I made a mockup of what the interface could look like at
http://people.ne.mediaone.net/rbromfield/kmeleon.bmp (yes, it it sadly a bitmap because all I had for the mockup was MS paint). It doesn't look fully like IE, but it's the most usable possible interface [in my opinion -]. Also, at
http://people.ne.mediaone.net/rbromfield/kmeleon.txt there's an overview of the menu structure, including four main menus. Notice the absence of context menus, for consistency between Mac and Windows interfaces (macs only have 1 button...)
This is probably old news, but what the hell.