I put EVERYTHING that is not a form control outside the form. Every time (well, not counting when I've been told to add "help text", which I then either stuff inside a form control or use ARIA to associate it). Users with a UA that has a "Forms Mode" will be getting only form controls inside the form, except ARIA-associated stuff.
I put the header outside (and above), I put the instructions outside (above! I hate when the instructions are at the bottom, I don't see that until after I've already filled everything in), and legend-text (like "fields marked with * are required").
*edit by "legend-text" I mean like a map legend, not the <legend> element
Only on simple, dedicated form pages would I consider letting the (lone) legend do that work (often if it's redundant I'll just hide the legend rather than not have a header).