Разница между блокировкой на уровне строки и на уровне таблицы важна только для запросов на вставку и обновление. Если вы в основном делаете выбор (поэтому вставки / обновления не случаются слишком часто для блокировки таблицы), разница будет не такой уж большой (даже если в недавних тестах InnoDB, кажется, превосходит MyISAM).
Другие способы, о которых вы могли бы подумать, - это реорганизовать структуру данных, возможно, добавив дополнительную справочную таблицу с тегами или ключевыми словами. Реализация более эффективного полнотекстового движка, как предложено webdestroya.
И последнее, но не менее важное: я также удивлен, что вы получили схожие результаты с FULL TEXT vs LIKE. Это может произойти, если поля, которые вы ищете, не очень широки, и в этом случае может быть достаточно стандартного индекса B-TREE с = search?