RewriteRule ^(.*)/video/ video.php?vid=$1 [L]
RewriteRule ^search/(.*)\.html search.php?q=$1 [L]

Bunların sırasını değiştirerek denermisin.
Aşağıdaki gibi;

RewriteRule ^search/(.*)\.html search.php?q=$1 [L]
RewriteRule ^(.*)/video/ video.php?vid=$1 [L]