Good to see that I’m not alone to have faced this strange problem.

We used ANALYZE TABLE as a solution in our case.

Thanks for the Percona Toolkit tip though!