Lo siento, pero no sé muy bien cómo usar el EXPLAIN. La consulta que causa los problemas es:
Código:
SELECT l.*
FROM #links_page AS l
LEFT JOIN #links_page_cat AS lc ON lc.link_category_id = l.link_category
WHERE l.link_class REGEXP '".e_CLASS_REGEXP."' AND lc.link_category_class REGEXP '".e_CLASS_REGEXP."' ".$cat."
GROUP BY l.link_id
ORDER BY link_numvotos
El únicco WHERE que hay no creo que sea el causante, lo que hace es sacar los enlaces de la categoría.