Ich hab noch ein bisschen gespielt und mein gesammeltes Wissen in eine Wiki-Seite geschrieben.
Virtuelle Wege einzutragen geht eigentlich ganz gut, die Rechenzeit ist für mich akzeptabel, 1 bis 2 Sekunden pro Platz (was bei mir heisst, der Import des Routing-Graphen dauert 20% länger), und wenn man die richtig komplizierten Fälle (etwa die Hecken in Ludwigsburg oder das Forum der hundert Treppen) überspringt, kann man das ganze wesentlich beschleunigen.
Ebenfalls deutlich beschleunigen kann man das Rechnen, wenn man seine Hindernisse sorgfältig auswählt. Man muss ja für alles, was so rumsteht überlegen, ob das einen Fussgänger ernsthaft aufhält. Jedes Loch in der Fläche, das dadurch entsteht, vervielfacht den Aufwand.
Ich hab das recht grosszügig betrachtet. Mit "amenity=* bildet jede Telefonzelle, Parkbank und jeder Papierkorb ein Hindernis. Bäume mit natural=tree ebenfalls. Häuser, Denkmäler, Flüsse, Trambahngleise sind auch Hindernisse und natürlich darf der Rasen nicht betreten werden.
Dabei habe ich auch gelernt, wie vielfältig die Welt der Plätze ist, vieles davon bleibt dem Betrachter verborgen, weil die Mapnik-Karte die Dinge entweder gar nicht rendert (amenity=fountain stehen häufig auf Plätzen, aber auch amenity=bicycle_parking können grosse Flächen einnehmen) oder sie unter den priorisierten highway-Flächen versteckt (Wintersportstätten oder Bäche z.B.).
Herzlichen Dank für die Vorschläge hier, besonders an Netzwolf, der interessante Dinge über Winkel erzählt hat (ich habe Tage damit verbracht, das als Unsinn zu entlarven, bevor ichs dann doch eingebaut hab 
) und couchmapper, der Dijkstra zum Löschen unnötiger Wege vorgeschlagen hat.
Der Routing-Graph über den Sebastians- und den Jakobsplatz, den ich oben als Beispiel verwendet habe, sieht übrigens jetzt so aus:
Die dicken blauen Linien sind die bereits gemappten Wege, die dünnen die zusätzlichen virtuellen.
Und wer mal selbst Routen will, kann mit diesem oder diesem Beispiel anfangen (die Geschwindigkeit liegt nicht an den paar tausend virtuellen wegen, das war schon vorher so… und wenns gar nicht geht, liegts daran, dass ich auch grad dran rumbastel…)
Grüße, Max
Nachtrag: Übrigens kann man an allen Plätzen, bei denen schon Wege drüber gemappt wurden, eher wenig Verbesserung durch automatisch eingetragene Wege erzielen. Bei vielen wurden aber einige Nebenstrassen einfach vergessen.