1. Ну про LIKE все сказали. Это очевидно. Теперь уже очевидно.
2. Что у вас с оперативкой на VPS? Что за ОС?
3. Убейте все расширения Apache и PHP которыми не пользуйтесь. Много это не даст, скажу честно.
4. Сколько у вас запросов приходится на одного пользователя при его обращении к одной странице!? А то вдруг у вас история как у vBulletin нашпигованного модами!? По 50 запросов с одного обращения пользователя.
5. Индексы в БД везде есть!? Может дополнительные сделать!? Пусть размер БД увеличится, зато скорость может подрасти.
Больше информации сообщите публике. А то все к LIKE и будут придираться.
