Ho risolto (grazie a un commento, il n°2) il problema dell'ordinamento: con le tabelle temporanee (e tre query in più) ora ho la certezza che l'ordinamento sia sempre perfetto:
Codice PHP:
// $a e $b sono le due grosse SELECT, con un paio di AS in più, che prima univo tramite UNION
mysql_query("CREATE TEMPORARY TABLE t0 $a", $db);
mysql_query("INSERT INTO t0 $b", $db);
mysql_query("CREATE TEMPORARY TABLE t2 SELECT * FROM t0 ORDER BY date DESC", $db);
mysql_query("SELECT * FROM t2 GROUP BY catid ORDER BY date DESC", $db);
Bello ed efficace 
Ora che la query è a posto, sorge un dubbio:
se due utenti contemporaneamente accedono allo script e creano tabelle temporanee che hanno lo stesso nome, queste "vanno in conflitto" oppure ogni utente ha "la sua zona dove creare le tabelle temp"? Devo dare nomi casuali (random o meglio =sid) alle tabelle temporanee?