Уличная магия с полным ее... в общем, полным.
У ТП хостера наконец дошли руки до моего тикета... и вдруг все заработало.
Тот же самый запрос выполняется, как положено, за миллисекунды.
В тех переменных, которые можно увидеть по SHOW VARIABLES, никаких изменений не произошло.
Единственная зацепка насчет причин - на старом сервере был MySQL 5.6, на новом - 5.7.
Впрочем, на сервере разработки у меня вообще MariaDB 8, и оно ему ни разу не мешало.
Спасибо за участие, джентльмены. Это было что-то выше нас ;)
P.S. График нагрузки у хостера через неделю. Явно видно, что конкретные запросы были ни при чем...