"Si no pongo el margen interno, padding, ¿como consigo q el texto esté separado del border de la celda?."
Poniendo este padding de 15px sobre el enlace, como lo dijé antes.
"Sobre lo de no usar tablas para posicionar elementos, ¿como es recomendable?"
El HTML declara una estructura, las tablas sirven para mostrar datos "tabulares", como por ejemplo cifras, un calendario o datos extraidos de una base de datos. Las tablas no se deben para colocar elementos, eso es el papel de la pareja div/css.
Mira el codigo fuente de esas webs para ver como se hace un menu sin tablas:
http://www.betanews.com/ http://www.adaptivepath.com/ http://www.onetruefit.com/