Вам нужно сделать два перенаправления, так как вы, вероятно, хотите, чтобы последний также распознавал первый:
# /search.php?search_term=foo to /search/foo/
RewriteCond %{THE_REQUEST} ^GET\ /search\.php\?([^& ]*&)*search_term=([^& ]*)
RewriteRule ^/search\.php$ /search/%2/ [L,R=301]
# /search/foo/ to /search.php?search_term=foo
RewriteRule ^/search/([^/]+)/$ search.php?search_category=0&search_term=$1&submit_search [L]