Гуглил, экспериментировал, экскрементировал кирпичами весь день.
MySQL версии 5.1.66, БД была создана запросом:
CREATE DATABASE DbName CHARACTER SET utf8 COLLATE utf8_general_ci;
SET NAMES 'utf8';
SELECT `id` FROM TableName WHERE LOWER(`title`) LIKE LOWER('%$search%');
SELECT `id` FROM TableName WHERE `title` LIKE COLLATE UTF8_GENERAL_CI = '%$search%';