<table style="width:100%;height:100%">
<tr>
<td style="vertical-align:middle">
<table>
<tr>
<td>Hola</td>
</tr>
</table>
</td>
</tr>
</table>
100% XHTML Válido.
De hecho los estilos podrías llevarlos a pasear a un archivo externo y llamarlos con id's o classes
;)