Какие существуют способы оптимизации часто идуших MySQL запросов на выборку?
Сферический вопрос в вакууме, причём без возможности уточнения, поскольку «проект был».
«медленные запросы» — насколько медленные?
«сайт с посещаемостью» — с какой посещаемостью? 
«потому что запросы на поиск» — так может, это поиск вынести отдельно на Сфинкс?

То есть, выяснить, что там — кривая настройка сервера mysql, кивые таблицы или кривые запросы — не представляется возможным.
Но вопрос, как всегда, формируется в самом общем виде — «где тот волшебный гвоздь, по которому 1 раз ударить — и всё сразу залетает?»

Ну ок. В самом общем виде оптимизация запросов (неважно — частых или нечастых) заключается в оптимизации запросов.
Оптимизированный запрос выполняется (допустим) 0.001 секунды. То есть, БД может обслужить 60 тысяч одновременно сидящих пользователей.

Берем EXPLAIN и смотрим. Если он говорит, что с запросом все окей, просматриваем ровно столько записей, сколько нужно — 5-10, но все равно запрос исполняется медленно (насколько конкретно медленно — в секундах?) то смотрим, SHOW ENGINE [engine] STATUS. Там уже надо опять же смотреть по месту, решать, чего серверу не хватает.

После того, как мы убедились, что все меры по оптимизации SQL приняты, то только тогда занимаемся кэшированием, заменой полл на пуш и т.д.

То есть, действуем как программист  — а именно, разбираемся с конкретной проблемой, и ищем решение конкретно для неё. 
А не придумываем от балды заплатку для лечения симптома, оставляя болезнь развиваться и дальше.

Кэширование, как и любая другая денормализация данных, всегда чревато проблемами и неудобствами. И это должно быть средство последней надежды, когда всё остальное уже сделано.
Если кэширование запросов не возможно то есть несколько путей (по степени эффективности ниже — эффективнее):
1. С помощью explain SQL посмотреть и удостоверится, что все запросы и индексы оптимальны. Если не оптимальны — оптимизировать. 
2. Использовать Шардинг (разбить таблицу на несколько) 
3. Кэширование 
4. Использование push-pub сервиса
5. использование middleware (на ноде, перле, жаве итп обернуть все операции с таблицей в RPC. требование к middleware — внутреннее кэширование всех данных, отправка только insert/update на mysql)