Si no me equivoco, puede ser que el alto que le has asignado al cuadro del menu, es superior por el abordado por las imagenes, y al poner "vertical-align: middle;" las imagenes se distributen por toda la capa, y pues por eso el hueco. Puedes poner una altura automatica, para que se ajuste al tamaño del conjunto de imagenes.
PD: Podrias poner de esta manera tu html, quedaria más práctico:
Código:
<div id="cuadro_menu">
<a href="vinos.php" class="borde"><img src="images/vinos.gif" alt="vinos" border="0" vspace="0"></a>
<a href="carta.php" class="borde"><img src="images/carta.gif" alt="vinos" border="0" vspace="0"></a>
</div>