sagt explain was unterschiedliches bei "possible keys", mit und ohne
SQL_CALC_FOUND_ROWS?
wenn ja, kannst du den index mit force index erzwingen.
wenn nicht, versuch mal das normale select und danach ein count
ohne limit und order zu machen und guck, ob das zusammengezählt schneller ist.\n\n

<!--EDIT|pq|1179092902-->