La mejor manera que he visto de centrar una tabla (o cualquier contenido) verticalmente en la ventana del navegador, es la siguiente.

En tu hoja de estilos pon estas dos clases:

.horizonte
{
color: #000000;
background-color: #ff0000;
text-align: center;
position: absolute;
top: 50%;
left: 0px;
width: 100%;
height: 1px;
overflow: visible;
visibility: hidden;
/*visibility: visible;  Activa esta linea si quisieras ver donde esta el horizonte*/
display: block;
}
 
.contenido
{
 
margin-left: -250px;
position: absolute;
top: -250px;
left: 50%;
width: 500px;
height: 500px;
visibility: visible;
}

La clase llamada horizonte posiciona contenido exactamente en la mitad de la pantalla, esto lo logra con el top=50%; Su altura es un pixel y su visibilidad es hidden porque no queremos que se vea, es solamente un lugar donde posicionaremos nuestro contenido. Ojo: Como su overflow es visible no importa que el contenido sea más alto que un pixel, más información sobre esto aquí.

Lo que debes de modificar en la hoja de estilos anterior es el width y el height de acuerdo a tu contenido. Cuando lo hagas, también modifica margin-left y top. Nota que son los mismos valores que width y height pero divididos entre 2 y con número negativo.

Y este es el código donde colocas tu información:

<div class="horizonte">
   <div class="contenido">
      <table width="500" border="1" height="500">
         <tbody>
            <tr>
               <td align="center" valign="middle">
               Esto es una tabla.
               También podría ser un DIV o cualquier otro elemento.
               De igual forma se centraría horizontal y verticalmente en la página.
               </td>
            </tr>
         </tbody>
      </table>
   </div>
</div>

Aquí también modifica width y height en la tabla para que concuerden con los valores que pusiste en la hoja de estilos.

* Funciona en Internet Explorer y Firefox.