Igaz elég régi az írás, de: MyISAM vagy InnoDB (esetleg más) engine-t használtál a táblákhoz? Úgy tudom, hogy az InnoDB jobban kezeli a subquery-ket, lehet csak ennyi volt a gond.