Seo em site pronto

Estou estudando php e consegui fazer um site localmente(servidor apache) e tudo, para implementar futuramente Ajax resolvi desenvolver um site onde todas as páginas são carregadas dentro de uma div na index.php(http://localhost/index.php?pag=home, ?pag=cad,...), faz conexão/inserção/atualização/remoção da base de dados, até aí tudo ótimo. O problema começou quando eu li algo a respeito de URL's Amigaveis e resolvi me aprofundar no assunto, já li vários tutorias a maioria bem legais, porém, enquanto estava na parte de adicionar as páginas

.htaccess

RewriteEngine On

RewriteRule ^([^/]*) index.php?pag=$1

de: http://localhost/index.php?pag=cad

para: http://localhost/cad

tudo uma maravilha eu simplesmente chamava o link assim <a href="cad">Cadastrar</a> e pronto, agora quando eu chamava as paginas para o acesso ao banco de dados como <a href="listar/categorias">Listar Categorias</a>

.htaccess

RewriteEngine On

RewriteRule ^([^/])/([^/]) index.php?pag=$1&tipo=$2

de: http://localhost/index.php?pag=listar&tipo=categorias

para: http://localhost/listar/categorias

Nesse exato momento começa minha peregrinação, veja o exemplo do que acontece:

Se eu clicar em Cadastrar vai para http://localhost/cad e se eu clico em Listar Categorias vai para http://localhost/listar/categorias.

Agora se eu clicar primeniro em Listar Categorias vai para http://localhost/listar/categorias e depois se eu clicar em Cadastrar vai para http://localhost/listar/cad, ou seja ele não vai para http://localhost/listar/categorias como deveria, ao invés disso ele adiciona o parametro cad na página listar.

Já vi o tópico http://forum.imasters.com.br/index.php?showtopic=203965 porém lá fala que:

"Atenção:

Há uma desvantagem em usar URLs amigáveis você tem que em todos os links colocar o caminho completo ..." acredito que se eu por o caminho completo nos links não vai dar para implementar Ajax futuramente, mas eu vejo no proprio site do iMasters(http://imasters.com.br/) que se você está em uma página do tipo: http://imasters.com.br/secao/tableless/ e clicar em um link para ir para http://imasters.com.br/secao/php/ ele vai direitinho

Alguém pode me explicar por que acontesse isso e principalmente, como resolver?

Agradeço profundamente a atenção de todos.