И строка поиска и строка массива в utf-8?
В документации ни слова не сказано про то что функция не поддерживает multibyte,
поэтому или проблема описанная выше, или внимательно проверять что хранится и что ищется, может быть с HEX редактором.
Ну и цитата:
Warning
This function may return Boolean FALSE, but may also return a non-Boolean value which evaluates to FALSE, such as 0 or "". Please read the section on Booleans for more information. Use the === operator for testing the return value of this function.