Solo necesitas esto:
Código:
Options +FollowSymLinks
RewriteEngine on
RewriteRule ^categoria/cat/(.*)$ categoria/index.php?cat=$1 [R=301,L]
La ultima linea esta de mas y solo te crea un loop infinito. Con esta linea especificas que el Redirect es permanente. Si google tiene indexada una pagina "index.php?cat=XXX" y ahora la ve con "categoria/cat/XXX", al ver el codigo 301, entendera que ahora el URL actual es "categoria/cat/XXX".
Y en todo caso, si quieres hacer redirecciones que pueden terminar en loops infinitos, debes usar un RewriteCond antes donde prevengas esa posibilidad.