quando generi i link generali mettendo l'id in coda dopo una / (così il rewrite lo trova) e prima metti il titolo opportunamente "filtrato" (elimini caratteri speciali, etc. e lo rendi tutto minuscolo), tipo:

Codice PHP:
$id = ...
$titolo = ...
$link = "..../?id=$id"; // adesso è così, invece (potresti usare le regexp, se riesci...):
$titolo = strtolower(trim($titolo));
$titolo = str_replace(array(' ', 'à', 'è', 'é', ...), array('-', 'a', 'e', 'e', ...), $titolo); // sostituzioni
$link = "..../$titolo/$id";