It's completely legitimate to have an input tag outside of a label. Even the link you provided states:

The HTML <label> Element represents a caption for an item in a user interface. It can be associated with a control either by using the for attribute, or by placing the control element inside the label element.

As long as you use the for attribute, it's fine.

Yes, quite right. I probably wasn't clear enough there, but I was referring to this from the article:

  <input type="text" required><label>Social Security Number</label></input>

Should be marked up as

  <label>Social Security Number<input type="text" required /></label>

if you want to omit the 'for' attribute.

Doing it the wrong way around will still render as you expect, but defeats the purpose as you won't get the click-to-activate behaviour.

Ah yes, that's horribly, horribly wrong. :)