Что именно не работает? Что-нибудь происходит?
Я не уверен на 100%, но я думаю, что вы должны сделать это так:
search-(.*?)-(.*?)-(.*?)\.html search.php?key=$1&type=$2&page=$3
Обратите внимание на ?
за звездочками. Это указывает на совпадение строки как раннего , насколько это возможно.