Right and correct markup in html forms

Once upon a time in HTML

I was looking W3Fools and find this paragraph, related to the errors in W3Schools:

  <form>  
    First name: <input type="text" name="firstname" /><br />  
    Last name: <input type="text" name="lastname" />  
   </form>
This code is wrong. Non-block-level elements (such as <input>) are not valid directly inside <form> tags until HTML5.

Well, since I always format that way I said to myself "WAIT, I was wrong all this time". And go to validate it to check if it's true. Efectively, this code don't pass the validation.

Then, searching for the correct markup, I found several examples from more reliable sources, but none of the following examples passes the validator.

The bad, the good and the ugly

1. W3Schools

<form>
First name: <input type="text" name="firstname"><br>
Last name: <input type="text" name="lastname">
</form>

2. Mozilla Network Developer

In "Examples" section, I have found this:

A common use-case senario

<!-- A common form that includes input tags -->
<form action="getform.php" method="get">
    First name: <input type="text" name="first_name" /><br />
     Last name: <input type="text" name="last_name" /><br />
        E-mail: <input type="email" name="user_email" /><br />
<input type="submit" value="Submit" />
</form>

3. W3C Wiki

<form action="http://www.google.com/search" method="get">
  <label>Google: <input type="search" name="q"></label>
  <input type="submit" value="Search...">
</form>

A Fistful of Codes

More details:

I'm trying to validate the code as HTML fragment, both in HTML 4.01 and XHTML 1.0. The recurring error I have found is:

document type does not allow element "input" here; missing one of "p", "h1", "h2", "h3", "h4", "h5", "h6", "div", "pre", "address", "fieldset", "ins", "del" start-tag

The question

What is the correct and valid markup I should use to make a form?

Thanks in advance.

Edit:

A similar question was answered redirecting the OP to the form section of HTML4 specification. They provided this code:

<FORM action="http://somesite.com/prog/adduser" method="post">
   <P>
     <!--...stuff...-->
     <INPUT type="submit" value="Send"> <INPUT type="reset">
   </P>
</FORM>

First, it isn't the same code of their wiki. But nevermind, from I know, the wiki it isn't 100% accurate.... BUT:

They fix the validation error by enclose all tag in a <p>. But forms are not paragraphs, it isn't? This code pass validation, but I think that's not very semantic...
Expert answers you giving to me (thanks!), for the most part, are to enclose the inner tags in a <fieldset>, but if I only need one fieldset (for example, a form with only one field or self-related fields), is this correct? Might that not be superflous code (because the fieldset tags are supposed to enclose similar fields)?

Solution

A fieldset is a block level element that is commonly used in forms. Therefore you could use a fieldset or another block level element like a div.

<form action="http://www.google.com/search" method="get">
<fieldset><legend>My form</legend>
<label>Google: <input type="text" name="q"></label>
<input type="submit" value="Search...">
</fieldset>
</form>

<form action="http://www.google.com/search" method="get">
<div>
<label>Google: <input type="text" name="q"></label>
<input type="submit" value="Search...">
</div>
</form>

This probably rarely gets flagged as non valid markup because people tend to a lot of divs to help style forms nicely.