Prueba a darle a tu cabecera un alto determinado en pixeles que comprubes que va bien para todo tipo de navegadores y tamaños de letra.
Así:
Código:
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="25%" rowspan="2" valign="top">Menu</td>
<td height="100" valign="top">Cabecera</td>
</tr>
<tr>
<td valign="top">Contenidos</td>
</tr>
</table>
Lo de alinear a top no es necesario, pero te lo recomiendo, ya que si el texto de los contenidos es muy largo, por defecto, el texto del menú aparecerá centrado verticalmente en su celda y puede que no se vea entero.
Suerte.