Con la misma clase, si quieres que se pinte todo el fondo, es obvio que debes quitar el padding, por cierto el margin no hará falta.
Código HTML:
<table class="navenlace" border="0" cellpadding="0" cellspacing="0">
<tr><td><a href="#">Tedddddddddddddxt</a></td></tr>
<tr><td><a href="#">Tedxt</a></td></tr>
<tr><td><a href="#">Teddddddddxt</a></td></tr>
</table>