Ну вообще, браузер будет сам их кодировать, когда нужно будет отправить данные на сервер, при этом отображать может продолжить как обычную кириллицу.
Проблемы могут возникнуть не на вашей стороне. Например, форумы на phpBB не считают ссылкой то, что содержит кириллицу. Правда, это уже не ваша проблема.
Ну и еще думаю как редирект сделать со старого наименования тэга на новый. пока в голову пришло только проверять наличие знаков процента в строке
Ну вообще, вы можете завести отдельное поле в БД под кириллический slug. Хотя, возможно, я не понял сути вопроса.