Moin,
sowohl aus Zeitmangel als auch aufgrund der Tatsache, dass ich kein Nominatim-Insider bin, kann ich nur ein paar grundlegende Infos weitergeben, die ich erforscht oder aufgeschnappt habe.
Nominatim ist die (bzw. eine) Suchmaschine von OSM.
OSM ist ja nur eine Datenbank, quasi ein Buch mit Hunderten von Seiten, Tausenden von Wörten und Abertausenden von Buchstaben - aber ohne Inhalts- und Stichwortverzeichnis!
Nominatim ist nun einerseits der Ersteller von Inhalts- und Stichwortverzeichnis - und andererseits der Blick in eben diese, wenn man etwas Bestimmtes sucht.
Nähere Infos findet man, wenn man den Suchergebnis-Links folgt, u. a. zu http://nominatim.openstreetmap.org und dort den weiterführenden Links Documentation und FAQ.
Auch bei http://open.mapquestapi.com/ findet man einige Infos zu Nominatim, auch dort muss man ein wenig graben.
Unvollständig heißt, dass eben noch nicht alle Verweise enthalten (erstellt) sind - alle Straßen innerhalb einer boundary müssen ja diese boundary als Parent haben.
Ein (z. Z.)vollständiger Index ist z.B. http://open.mapquestapi.com/nominatim/v1/details.php?place_id=79464406.
Die Erstellung eines Index ist ja auch aufwändig und kostet Zeit. Nominatim ist da zwangsläufig dem reinen Datenbestand sicherlich um ein paar Tage - evtl. auch mal Wochen - hinterher. Nicht nur dem OSM-Datenbestand, sondern ja auch dem Nominatim-eigenen Datenbestand.
Data: 2011/08/19 bei Nominatim heißt ja nur, dass sie den OSM-Datenbestand von diesem Datum berücksichtigen (Nominatim-eigener Datenbestand) - aber noch lange nicht, dass auch dessen kompletter Index bereits erstellt ist.
Schwarz sind m. W. die berücksichtigten Kriterien, grau sind weitere Kriterien, die aber nachrangig gewichtet wurden (siehe auch der Rank/die Wichtung vor dem GOTO-Link).
Vielleicht hilft es, sich anhand eines einfachen Szenarios mal die Vorgehensweise selbst zu erarbeiten.
Ein Adress-node, eine Straße, ein place-node (Ortsteil), ein weiter entfernter Place-node (Hauptort) und die zugehörige Gemeinde (boundary-relation mit gleichem Namen) drumherum.
Und jetzt findet mal anhand der vorhandenen oder eben auch mal nicht vorhandenen Informationen (Tags und Objekte) heraus, wo sich dieser Adressnode oder diese Straße befinden.
Mal mit address:city, mal ohne. Mal mit boundary-relation, mal ohne.
Dabei sind die place-nodes und die boundary auf gleicher Ebene, aber eben mit unterschiedlicher Wichtung zu werten!
Edit1:
Dass sich Adresse oder Straße in der Nähe vom place-node oder innerhalb der boundary befinden, sieht man als Betrachter zwar auf Anhieb - aber Nominatim muss sich dieses logische Wissen eben erst erarbeiten - und Buch (Index) darüber führen, damit nicht bei jeder neuen Abfrage der gesamte Datenbestand neu untersucht (erarbeitet) werden muss.
Ansonsten: Viele Eurer Fragen stelle ich mir selber noch … 
Gruß
Georg