Io farei qualcosa del genere:

codice:
RewriteEngine on
RewriteRule ^/(.+?)/(.+?)/(.+?)/?$ /pagina.php?s=$1&c=$2&a=$3 [L]
RewriteRule ^/pagina.php?s=(.*?)&c=(.*?)&a=(.*?)$ /$1/$2/$3/ [R=301]
In teoria non dovrebbe generare alcun rewrite ricorsivo e dovrebbe funzionare correttamente.
Il primo rewrite è quello classico e il [L] interrompe l'esecuzione per i rewrite successivi. Il secondo, che viene processato solo se il primo fallisce invece è un redirect al nuovo indirizzo.