Как оптимизировать сложный запрос на нагруженной базе MYSQL?

Сравните EXPLAIN-ы.

У меня не захотел подтягиваться индекс во второй таблице даже через FORCE INDEX c  NOT EXISTS, хотя у вас как бы тянет.

Но смущает длина индекса по первой таблице

не похоже на пробелму с индексами, такая конструкция как сейчас спокойно выдерживает 2-3к одновременных селектов. Если подваливает под 4к+ начинает сильно нагружаться процессор, как будто нехватает ресурсов

Судя по запросу в том виде как Вы его привели, у Вас только одна переменная там -

$acc 

Если это реально так, то создайте таблицу сделаную по этому же запросу, но без учета этой переменной. И работайте по ней.
Если получается большая, то вынесите в новую таблицу только важные вещи - ключевик для выборки по основной таблице и $acc.

Эта переменная динамическая. просто вырвана из контекста кода. Доупстим там 84378234, а в след запрос 78432878

Дык мы об этом и говорили. Но остальной запрос статичен? Если да, то при такой нагрузке есть смысл вытащить данные по нему в отдельную таблицу. Апдейтить ее по времени или по триггерам.
Или для начала просто попробовать вьюху сделать, а не отдельную таблицу как таковую. Вьюхи неплохо кэшируются, если памяти достаточно.

запрос статичен, выборка меняется по 4000 раз в секунду из за инсертов туда

Почему-то возникло ощущение, что это у вас нечто вроде сервиса очередей, правы, нет? Если да, то есть смысл в специализированном решении.
Что касается непосредственно решения задачи из первго поста, то кроме уже предложенного кэширования данных этого статичного запроса (если это допустимо), тут тяжело что-то предложить.

Единственное что бы мы еще проверили - насколько у вас сеть между мастером и слейвами забита. Потому что частота запросов достаточно высокая, что бы в принципе даже широкий канал между серваками забить. И в таком случае возможно все упирается не в саму скорость обработки базой, а в то что сетевой интерфейс тормозит. А проц нагружен от того, что ему приходится огромное количество данных пропихивать в недостаточной ширины сетевой интерфейс.

У нас не сервис очереди но сервер очередей используем в разных целях (Rabbitmq). У нас сервис по взаимопиару в социальных сетях.

Сеть не забита, сервера в 1 стойке.