Если вы хотите, чтобы Apache принимал закодированные слеши, как вы упомянули в комментариях, вам нужно включить его в конфигурации вашего сервера с помощью директивы AllowEncodedSlashes :
AllowEncodedSlashes on
Вероятно, вы сейчас не включили это, и в этом случае стандартное поведение - Apache отклонить запрос с ответом 404. Вы можете указать эту директиву только в контексте сервера или виртуального хоста, поэтому в зависимости от вашей среды вы не сможете ее изменить. Что касается закодированного хеш-символа, у него не должно возникнуть проблем с обработкой этого.
Однако, вероятно , что хеш вставляется в декодированную строку запроса, что может вызвать некоторые проблемы. Если вы обнаружите, что это так, и ваша установка Apache является достаточно новой, вы должны добавить B flag к вашему RewriteRule, чтобы убедиться, что обратная ссылка экранирована надлежащим образом:
RewriteRule ^search/(.*)-([0-9]+).html$ index.php?search=$1&page=$2 [B,L]