Formulario css xhtml a dos columnas

Hace tiempo que cuando tenía que hacer un formulario aún recurría a maquetar con tablas. pero hoy he intentado hacerlo por fín con css.
Básicamente jugando con float:left; y display:block, para los elementos label y dejando de lado los inputs.

El código html sería el siguiente:

<div id="contacto">
<form id="Form" action='mailform.php' method='post' onsubmit="return checkform(this)">
<fieldset>
<legend>Contacto</legend>
<label for="nombre" class="nombre">Nombre</label>
<input id="nombre" class="borde" name="nombre" value="" maxlength="100" type="text" /> <br />
<label for="email" class="" email">Email</label>
<input id="email" class="borde" name="email" value="" maxlength="100" type="text" /> <br />
<label for="telefono" class="telefono">Teléfono</label>
<input id="telefono" class="borde" name="telefono" value="" maxlength="100" type="text" /> <br /><br />
<label for="mensaje" class="mensaje">Mensaje</label>
<textarea id="mensaje" class="borde" name="mensaje" cols="58" rows="8"></textarea><br />
<input id="Submit" name="contact_submit" value="Envía" type="submit" />
</fieldset>
</form>
</div>

y parte del css requerido sería este:

form fieldset label{
margin-top:2px;
display: block;
float: left;
text-align: left;
width:70px;
/*border:1px solid #11aa33;*/
font-size:13px;
height:10px;
}

Hay una web que trata bastante más profusamente el tema: form two columns