Вопрос закрыт, проблема была в конфигурации MySQL, как я и предполагал, а не в индексах, или построении запросов.
Изменили под наш конфиг машины данные параметры MySQL:
1) max_allowed_packet увеличили (до 64мб)
2) key_buffer_size увеличен (до 64мб)
3) innodb_buffer_pool_size значительно уменьшен (до 4гб)
4) max_connections значительно увеличены (до 10000)
5) query_cache_size увеличен (до 16мб)
А также добавили и включили файл подкачки, но он пока не задействован, т.е конфиг сделал главное дело.
