Seguramente sea porque debiera ir así:
Código .htaccess:
Ver originalRewriteEngine On
RewriteRule ^/story/(.+)$ /story.php?$1 [L,NS]
RewriteRule ^/user/(.+)$ /user.php?$1 [L,NS]
RewriteRule ^/search(/.*)$ /index.php?$1 [L,NS,NE,PT]
Incluso, seguramente, los nombres de la variables tal vez sea en realidad el valor de las variables.
Código .htaccess:
Ver originalRewriteEngine On
RewriteRule ^/story/(.+)$ /story.php?var=$1 [L,NS]
RewriteRule ^/user/(.+)$ /user.php?var=$1 [L,NS]
RewriteRule ^/search(/.*)$ /index.php?var=$1 [L,NS,NE,PT]
Y, por cierto, para simplicar, incluso podrías poner las dos primeras reglas en una sola:
Código .htaccess:
Ver originalRewriteRule ^/(story|user)/(.+)$ /$1.php?var=$2 [L,NS]