1) Сомневаюсь, что вы используете mysql 3-ей версии, а ведь исключительно для поддержки совместимости с этим старым хламом расширение mysql ещё есть в некоторых не свежих версиях пхп. А так оно устарело в районе 5-10 лет, используйте mysqli.
2) у вас расхождение в вопросе, в скрипте вы смотрите количество строк в ответе, а при при выполнении запроса руками смотрите на результат. Тёплое с мягким не находите?
3) Ваша проблема в кодировках, а правильный вопрос почему не ищет кириллицу. Ваша проблема скорее всего в неверном character set и collotion на стороне mysql, которые могут быть выставлены на уровне сервера, бд, таблицы и поля (если не определено внизу, то берётся значение сверху). И ещё более вероятно, что вы залили или пишете utf дамп/данные в базу которой кодировка latin или cp1251 (они обе совпадают с utf8 в части латиницы) в этом случае на клиенте всё как бы ок, а кириллицу mysql не понимает.