Risolto, in effetti era un problema di indici. Pur essendoci gli stessi indici, in locale non dava problemi, in remoto, era estremamente lento. Dopo l'utilizzo della EXPLAIN sulla SELECT ho aggiunto un ulteriore indice e la query è diventata una scheggia.
Grazie a tutti
P.S. Non so come aggiungere "RISOLTO" al titolo del post