primero que todo "A" no es lo mismo que "a" para los navegadores que respaldan 100% el CSS, eso debes cambiarlo.
Lo segundo es que debes aplicarle la clase a la celda y no al link.
Saludos,
PD: también puedes resumir tu código y dejarlo así:
Código:
table {border: 1px solid #BCCFDE; background-image:url (images/BtnFondo.jpg); width: 100%;}
td {width: 50%; text-align: center}
table, tr, td {border-collapse: collapse;}
.menu a:link, .menu a:visited, .menu a:active {text-decoration:none; color:black; display: block;}
.menu a:hover{font-weight:bold;}
.separador {border-right: 1px solid #BBAADD; display: block}
y la tabla queda así:
Código HTML:
<table>
<tr>
<td class="menu separador">
<a href="Pagina1.asp" >Pagina1</a>
</td>
<td class="menu">
<a href="Pagina2.asp">Pagina2</a>
</td>
</tr>
</table>