Пользуясь полнотекстовым поиском MySQL около 4 лет и просто переходя на Sphinx, я бы сказал, что обычный поиск MySQL с использованием полнотекстового логического (то есть точного) синтаксиса будет нормальным. Это быстро и будет делать именно то, что вы хотите. Количество данных, которые вы будете искать в любой момент времени, будет небольшим.
Единственной проблемой может быть упорядочение результатов. Полнотекстовый поиск в MySQL может замедлиться, когда вы начнете упорядочивать вещи по (например) дате, так как для этого требуется, чтобы вы искали всю таблицу, а не только первые nn найденные результаты. В конце концов, именно по этой причине я переехал в Сфинкс.
Sphinx также потрясающий, так что не бойтесь его попробовать, но, похоже, в вашем случае дополнительные функции могут не потребоваться.