Отношение поисковиков к кириллице (URL)

В Яндексе - нет.

http://help.yandex.ru/webmaster/yandex-indexing/cyrillic-urls.xml

Проблемы могут возникнуть при работе с зарубежными ПС.

Ни у Яндекса, ни у Гугла проблем, насколько мне известно, нет. Единственное, что могут быть всякие сложности в плане длины строки, т.к. кириллические символы кодируются в UTF и длина строки существенно увеличивается, соответственно если строка получится слишком длинной в некоторые формы её не вставишь, некоторые редиректы с ограничением длины строки на уровне сервера не сработают и тыды. Тобишь желательно не слишком увлекаться вроде site.ru/длинное-название-категории/длинное-название-раздела :)

Какого рода проблемы?