In IE6 and IE7, the legend is not rendered unless a wrapper div is placed inside the fieldset. However, when a div is placed enclosing the fieldset contents, the Legend is rendered, but a mysterious space appears between one of the Label and Input tags. A variety of hasLayout triggers has been attempted on the Legend element to no avail.
It looks a lot like a Peek-a-Boo bug, as the first Legend will occasionally be rendered. However, it isn't as predictable, nor do the expected fixes work consistently.
Setting the width of the input elements to an amount smaller than 100% (see below) apparently resolves the problem. However, in IE input tags, when children of fieldsets, inherit horizontal margins from the fieldset. That just ain't right...