Sachverhalt:
A. Am östlichen Ende der Wiesenstrasse im stadtzürcherischen Quartier Seefeld befinden sich auf der nördlichen Strassenseite, vor der Eckliegenschaft gegen die Mühlebachstrasse hin, drei aneinander anschliessende Parkplätze der Blauen Zone. Die Stadtpolizei Zürich hatte am 30. Juni 2005 im betroffenen Parkplatzbereich mittels mobiler Signaltafeln ein Halteverbot mit Wirkung ab 5. Juli 2005, 06.00 Uhr, ausgeschildert; es wurde angeordnet, um eine Bauinstallation zu ermöglichen. Dennoch stand das Auto von X._ am 5. Juli 2005 zwischen 08.10 Uhr und 09.25 Uhr in diesem temporären Halteverbot. Die Stadtpolizei liess ihr Fahrzeug abschleppen; am darauf folgenden Tag wurde es X._ im Parkhaus Hohe Promenade wieder zurückgegeben. Dafür auferlegte ihr die Stadtpolizei mit Verfügung vom 15. Juli 2005 eine Gebühr von Fr. 425.--.
B. Der Stadtrat von Zürich schützte auf Einsprache von X._ hin die Gebührenverfügung mit Beschluss vom 8. November 2006. Den hiergegen erhobenen Rekurs wies das Statthalteramt des Bezirks Zürich am 25. April 2007 ab, soweit es darauf eintrat. X._ zog den Rekursentscheid an das Verwaltungsgericht des Kantons Zürich weiter. Der Einzelrichter der 3. Abteilung des Verwaltungsgerichts hiess ihre Beschwerde mit Entscheid vom 17. September 2007 gut. Er hob die unterinstanzlichen Entscheide auf, soweit sie von der Beschwerdeführerin angefochten und nicht in Rechtskraft erwachsen waren. Der Einzelrichter am Verwaltungsgericht erwog zusammengefasst, die Gebühren hätten X._ nicht belastet werden dürfen, weil die Stadtpolizei vor dem Abschleppen des Fahrzeugs zu Unrecht keinen Versuch unternommen habe, die Betroffene zu kontaktieren.
C. Gegen den verwaltungsgerichtlichen Entscheid legt die Stadt Zürich beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten ein. Sie beantragt die Aufhebung des angefochtenen Entscheids und die Bestätigung der unterinstanzlichen Entscheide; eventualiter sei die Sache an das Verwaltungsgericht zurückzuweisen.
Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. X._ ersucht darum, auf die Beschwerde nicht einzutreten; eventualiter sei diese abzuweisen.
Erwägungen:
1. Auf das Beschwerdeverfahren ist das Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (BGG; SR 173.110) anwendbar (vgl. Art. 132 Abs. 1 BGG).
1.1 Die Beschwerde richtet sich gegen einen kantonalen Entscheid, der eine kommunale Gebührenverfügung für eine polizeiliche Massnahme zum Gegenstand hat. Dabei handelt es sich um eine öffentlich-rechtliche Angelegenheit im Sinne von Art. 82 lit. a BGG. Ausschlussgründe nach Art. 83 und 85 BGG liegen nicht vor. Der angefochtene Entscheid schliesst den kantonalen Instanzenzug ab (Art. 86 Abs. 1 lit. d BGG). Es geht um einen Endentscheid im Sinne von Art. 90 BGG, weil der beschwerdeführenden Stadt Zürich im Ergebnis verwehrt wird, von der privaten Beschwerdegegnerin eine Gebühr zu verlangen.
1.2 Der angefochtene Entscheid trifft die Gemeinde in ihren hoheitlichen Befugnissen. Sie kann sich daher über eine Verletzung ihrer Autonomie beklagen. In diesem Sinne ist sie gestützt auf Art. 89 Abs. 2 lit. c BGG zur Beschwerdeführung legitimiert. Ob und inwieweit ihr tatsächlich Autonomie zusteht, ist nicht eine Frage des Eintretens, sondern der materiellen Beurteilung (BGE 129 I 410 E. 1.1 S. 412 mit Hinweisen). Die Gemeinde kann im Rahmen einer Autonomiebeschwerde auch eine Verletzung des Willkürverbots, des Gehörsanspruchs oder anderer Verfassungsgrundsätze (Rechtsgleichheit, Treu und Glauben, Verhältnismässigkeit) geltend machen, soweit diese Rügen mit der behaupteten Verletzung der Autonomie in unmittelbarem Zusammenhang stehen (BGE 131 I 91 E. 1 S. 93; 129 I 290 E. 2.3 S. 295; 116 Ia 252 E. 3b S. 255, je mit Hinweisen).
1.3 Die Beschwerdeführerin beansprucht darüber hinaus auch eine Legitimation gestützt auf das allgemeine Beschwerderecht nach Art. 89 Abs. 1 BGG. Darauf muss nicht weiter eingegangen werden, weil die letztgenannte Bestimmung ihr hier keine zusätzlichen Beschwerdemöglichkeiten verschafft.
1.4 Die übrigen Sachurteilsvoraussetzungen sind erfüllt und geben zu keinen weiteren Bemerkungen Anlass. Auf das Rechtsmittel ist somit einzutreten.
2. 2.1 Nach der Rechtsprechung sind Gemeinden in einem Sachbereich autonom, wenn das kantonale Recht diesen nicht abschliessend ordnet, sondern ihn ganz oder teilweise der Gemeinde zur Regelung überlässt und ihr dabei eine relativ erhebliche Entscheidungsfreiheit einräumt. Der geschützte Autonomiebereich kann sich auf die Befugnis zum Erlass oder Vollzug eigener kommunaler Vorschriften beziehen oder einen entsprechenden Spielraum bei der Anwendung kantonalen oder eidgenössischen Rechts betreffen. Der Schutz der Gemeindeautonomie setzt eine solche nicht in einem ganzen Aufgabengebiet, sondern lediglich im streitigen Bereich voraus. Im Einzelnen ergibt sich der Umfang der kommunalen Autonomie aus dem für den entsprechenden Bereich anwendbaren kantonalen Verfassungs- und Gesetzesrecht (vgl. BGE 133 I 128 E. 3.1 S. 130 f.; 129 I 290 E. 2.1 S. 294, je mit Hinweisen).
2.2 Laut dem angefochtenen Entscheid stützt sich die Vorinstanz auf § 31 Abs. 2 und 3 des kantonalen Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 (VRG/ZH; LS 175.2). § 31 VRG/ZH steht im Abschnitt dieses Gesetzes über die Vollstreckung von Anordnungen der Verwaltungsbehörden. Abs. 1 der Norm verlangt, dass der Ersatzvornahme und der Anwendung unmittelbaren Zwangs eine entsprechende Androhung, unter Ansetzung einer angemessenen Frist zur Erfüllung, voranzugehen hat. Gemäss § 31 Abs. 2 VRG/ZH kann die Zwangsandrohung mit der zu vollstreckenden Anordnung verbunden oder selbständig erlassen werden; die Zwangsandrohung ist nicht durch Rekurs anfechtbar. § 31 Abs. 3 VRG/ZH bestimmt, dass in dringlichen Fällen von einer Zwangsandrohung abgesehen werden kann.
2.3 Die Vorinstanz hat im vorliegenden Fall die in § 31 Abs. 3 VRG/ZH vorausgesetzte Dringlichkeit bejaht. Nach ihren Darlegungen hat das Fahrzeug eine private Bauunternehmung daran gehindert, eine Materiallieferung abzuladen; das Halteverbot war auf Veranlassung dieser Firma verfügt worden. Diese Sachumstände bestreitet die Beschwerdegegnerin vor Bundesgericht nicht mehr konkret. Im angefochtenen Entscheid wird eingeräumt, dass die Stadtpolizei gestützt auf § 31 Abs. 3 VRG/ZH dem Grundsatz nach auf eine Zwangsandrohung verzichten kann. Im konkreten Fall hat die Vorinstanz aus Gründen der Verhältnismässigkeit dennoch eine Pflicht der Stadtpolizei zur vorgängigen Kontaktaufnahme mit der Autohalterin bejaht. Wie die nachfolgenden Erwägungen zeigen, verletzt diese Beurteilung die Gemeindeautonomie der Stadt Zürich.
2.4 Darüber hinaus macht die Beschwerdeführerin auf Art. 31 der Allgemeinen Polizeiverordnung der Stadt Zürich (APV) aufmerksam. Sie bringt vor, mit dieser Norm verfüge sie über eine kommunale Rechtsgrundlage für die Wegschaffung von verkehrsbehindernd abgestellten Fahrzeugen ohne vorgängige Zwangsandrohung. Es trifft zu, dass die Gemeinden nach § 74 des kantonalen Gemeindegesetzes vom 6. Juni 1926 (LS 131.1) befugt sind, im Rahmen der dort vorgesehenen kommunalen Polizeiverordnung auch Regelungen über Abschleppmassnahmen gegenüber Fahrzeugen zu treffen (vgl. Tobias Jaag/Markus Rüssli, Das Abschleppen vorschriftswidrig parkierter Fahrzeuge, am Beispiel der Stadt Zürich, AJP 2001 S. 1381 ff., 1382). Die Vorinstanz hat aber erwogen, in Art. 31 APV sei nicht klar geregelt, ob die Polizei vor dem Abschleppen mit dem Eigentümer des störenden Fahrzeugs Kontakt aufzunehmen habe. Im Ergebnis hat die Vorinstanz der kommunalen Vorschrift in diesem Punkt keine weitergehende Tragweite als dem Gehalt von § 31 VRG/ZH beigemessen. Da im konkreten Fall ein verfassungsrechtlich geschützter Autonomiebereich der beschwerdeführenden Stadt Zürich bereits im Lichte von § 31 Abs. 3 VRG/ZH besteht, kann offen bleiben, inwiefern der Regelung von Art. 31 APV in dieser Hinsicht eine eigenständige Bedeutung zukommt.
3. 3.1 Ist eine Gemeinde autonom, so kann sie sich unter anderem dagegen zur Wehr setzen, dass eine kantonale Behörde in einem Rechtsmittelverfahren ihre Prüfungsbefugnis überschreitet (vgl. BGE 129 I 410 E. 2.3 S. 414 mit Hinweisen). Dabei kann die Gemeinde, wie bei E. 1.2 hiervor dargelegt, weitere Verfassungsrügen erheben. Soweit es um die Handhabung von eidgenössischem oder kantonalem Verfassungsrecht geht, prüft das Bundesgericht das Vorgehen der kantonalen Behörde mit freier Kognition, sonst nur auf Willkür hin (BGE 132 I 68 E. 1.1 S. 69 f.; 129 I 410 E. 2.3 S. 414, je mit Hinweisen).
3.2 Die Beschwerdeführerin hält der Vorinstanz mit einlässlicher Begründung eine unrichtige und willkürliche Anwendung des Verhältnismässigkeitsprinzips vor. Nach der ständigen bundesgerichtlichen Rechtsprechung verlangt das Gebot der Verhältnismässigkeit, dass eine behördliche Massnahme für das Erreichen des im öffentlichen oder privaten Interesse liegenden Zieles geeignet und erforderlich ist und sich für die Betroffenen als zumutbar erweist. Erforderlich ist eine vernünftige Zweck-Mittel-Relation. Eine Massnahme ist unverhältnismässig, wenn das Ziel mit einem weniger schweren Eingriff erreicht werden kann (vgl. BGE 133 I 77 E. 4.1 S. 81, 110 E. 7.1 S. 123, je mit Hinweisen).
3.3 Mit Blick auf diese Praxis hat die Vorinstanz argumentiert, das störende Fahrzeug sei in der Nähe der Wohnung der Beschwerdegegnerin abgestellt gewesen; diese wohnt in einer Parallelstrasse zur Wiesenstrasse. Zudem habe sich im Fahrzeug gut sichtbar eine Anwohnerparkkarte befunden, die für die Blaue Zone im Bereich der Postleitzahl 8008 und damit für den betroffenen Standort ausgestellt gewesen sei. Es sei somit von vornherein ersichtlich gewesen, dass die Fahrzeughalterin in der Nähe wohne. Angesichts dieser Umstände sei die Stadtpolizei verpflichtet gewesen, einen Versuch zu unternehmen, die Beschwerdegegnerin telefonisch zu kontaktieren oder in ihrer Wohnung aufzusuchen. Da die Stadtpolizei keinen derartigen Versuch gemacht habe, erweise sich die Wegschaffung des Fahrzeugs als unverhältnismässig bzw. als rechtswidrig.
3.4 Das Fahrzeug der Beschwerdegegnerin war in einem Halteverbot und nicht nur in einem Parkverbot abgestellt (vgl. zur Tragweite dieser Unterscheidung Art. 30 der Signalisationsverordnung [SSV; SR 741.21]). Das Halteverbot war rechtzeitig ausgeschildert worden. Wie sich aus dem Rekursentscheid des Statthalteramts ergibt, wurde das Fahrzeug der Beschwerdegegnerin nachweislich erst nach Aufstellung der Signaltafeln dort parkiert. Derjenige, der das Fahrzeug damals dort parkierte, war aufgrund der Signaltafeln genügend vorgewarnt, dass er mit einer Abschleppung rechnen musste, und dieses Wissen hat sich die Beschwerdegegnerin anrechnen zu lassen. Bei einem Halteverbot besteht eine besondere Dringlichkeit, dass das störende Fahrzeug sofort polizeilich weggeschafft wird. Im Übrigen wurde die mit dem Halteverbot reservierte Fläche tatsächlich von Dritten benötigt. Der Umstand, dass eine fachgerechte Räumung durch den Abschleppdienst eine gewisse Zeit beansprucht, darf in solchen Fällen nicht ohne Weiteres dazu führen, dass der fehlbare Autohalter einen Rechtsanspruch auf eine vorgängige Zwangsandrohung erheben kann.
3.5 Es sind Konstellationen denkbar, in denen gegenüber dem Lenker bzw. Halter des Fahrzeugs, das im Halteverbot parkiert ist, eine Zwangsandrohung unabdingbar ist. Dabei gilt es zu berücksichtigen, dass die Polizeikräfte vorgängig den Verstoss gegen das Halteverbot festzustellen haben, bevor sie den Abschleppdienst aufbieten. Tritt der Lenker wieder zum Fahrzeug, während die Polizei eine solche Verkehrsregelverletzung feststellt und aufnimmt, so hat sie ihm Gelegenheit zu geben, das Fahrzeug selbst wegzustellen. Mit einer solchen Situation ist jedoch der blosse Umstand nicht vergleichbar, dass der Halter im Quartier wohnt, in dem sein Auto im Halteverbot parkiert ist. Folglich kommt der Anwohnerparkkarte für sich allein keine ausschlaggebende Bedeutung zu. Die Parkkarte vermag auch die Missachtung des Halteverbots in keiner Weise aufzuwiegen. Es ist zwar nicht zu beanstanden, wenn ein Polizeibeamter wegen der Anwohnerparkkarte dennoch zuerst die persönlichen Daten des Fahrzeughalters ermittelt und zum Telefon greift, weil er sich davon im Ergebnis eine schnellere Problemlösung verspricht. Die Vorinstanz als kantonales Gericht kann dies aber nicht verlangen, wenn die Stadt Zürich eine solche Pflicht weder generell noch im Einzelfall aufstellt. Die Vorinstanz hat demzufolge mit dem von ihr als allgemein massgeblich erklärten Kriterium der Parkkarte auf unhaltbare Weise in die verfassungsrechtlich geschützte Entscheidungsfreiheit der Stadt Zürich eingegriffen.
3.6 Ein anderes Ergebnis ist auch nicht aufgrund des im angefochtenen Entscheid erwähnten Urteils des Bundesgerichts 2P.192/2000 vom 29. November 2000 geboten. In jenem Fall war der Halter des Fahrzeugs an das Bundesgericht gelangt. Sein Fahrzeug war in der Stadt Zürich mehrere Parallelstrassen entfernt von seiner Wohnung in einem Halteverbot abgestellt. Die Signalisation war im Hinblick auf einen Wohnungsumzug aufgestellt worden. Zwei Polizeibeamte begaben sich zum Wohnort des Halters, nachdem sie vor Ort das vorschriftswidrige Parkieren festgestellt hatten. In der Wohnung trafen sie den erwachsenen Sohn an und teilten ihm mit, dass das Fahrzeug entfernt werden müsse. In der Folge kehrten sie zum Fahrzeug zurück, warteten vergeblich 10 bis 15 Minuten und forderten daraufhin den Abschleppwagen an. Das Bundesgericht wies die Beschwerde gegen die Auferlegung der Abschleppgebühren ab. Es führte in den Erwägungen aus, die Polizeibeamten hätten versucht, den Halter zu verständigen, und geraume Zeit gewartet, nachdem sie den Sohn des Halters zu Hause angetroffen hätten. Es könne vernünftigerweise nicht verlangt werden, dass sie noch länger hätten warten müssen (a.a.O., E. 2b). Aus jenem Urteil lässt sich nicht folgern, das Bundesgericht habe die damals zu prüfende Beschwerde einzig deshalb abgewiesen, weil die Polizeibeamten erfolglos versucht hatten, den Halter zu kontaktieren. Ob eine Notwendigkeit zur Zwangsandrohung bestand, war im damaligen Fall nicht zu prüfen.
4. Zusammengefasst verstösst es gegen die Gemeindeautonomie, wenn die Vorinstanz der Stadtpolizei hier zum Vorwurf macht, sie könne keinen dokumentierten Versuch nachweisen, dass sie die Beschwerdegegnerin zu kontaktieren versucht habe. Vor diesem Hintergrund ist nur kurz auf den Rügenkomplex der Beschwerdeführerin zur Sachverhaltsermittlung im angefochtenen Entscheid einzugehen. Nach der Beschwerdeführerin hat die Vorinstanz übersehen, dass der verantwortliche Bauleiter und ein Vorarbeiter ausgesagt hätten, es sei von Seiten des auf die Räumung angewiesenen Unternehmens privat versucht worden, die Halterin zu Hause aufzusuchen; diese sei dort leider nicht angetroffen worden. Mit diesen Vorbringen vermag die Beschwerde die Tatsachenfeststellung im angefochtenen Entscheid nicht zu erschüttern. Sowohl der angefochtene Entscheid wie auch die vorstehenden Erwägungen beruhen darauf, dass die Polizei verpflichtet ist, die Zwangsandrohung selbst auszusprechen. Die Polizei könnte sich den ihr im Rahmen von § 31 VRG/ZH obliegenden Pflichten nicht dadurch entschlagen, dass sie auf unbewiesene Behauptungen Privater abstellen würde, wonach bereits erfolglos versucht worden sei, den Halter zu erreichen (vgl. dazu das Urteil 1P.242/1997 vom 23. Juni 1997, E. 1b: in ZBl 99/1998 S. 138). Daher geht der ganze diesbezügliche Rügenkomplex fehl.
5. Nach dem Gesagten ist die Beschwerde gutzuheissen. Im angefochtenen Entscheid wird festgehalten, dass die Gebührenfolge und deren Höhe im Verfahren vor der Vorinstanz nicht mehr umstritten waren. Auch im bundesgerichtlichen Verfahren erhebt die Beschwerdegegnerin keine Einwände in diesen Punkten. Dies führt dazu, dass nicht nur der angefochtene Entscheid aufzuheben, sondern in der Sache direkt der Rekursentscheid des Statthalteramts zu bestätigen ist (vgl. Art. 107 Abs. 2 BGG). Dadurch wird insbesondere die Abschleppgebühr gemäss Verfügung der Stadtpolizei vom 15. Juli 2005 rechtskräftig (Art. 61 BGG).
Bei diesem Verfahrensausgang trägt die unterliegende Beschwerdegegnerin die Kosten des bundesgerichtlichen Verfahrens (Art. 66 Abs. 1 BGG). Ihr sind ebenfalls die von der Vorinstanz festgesetzten Gerichtskosten aufzuerlegen (Art. 67 BGG). Der obsiegenden Beschwerdeführerin steht keine Parteientschädigung zu (Art. 68 Abs. 3 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Zürich, 3. Abteilung, Einzelrichter, vom 17. September 2007 wird aufgehoben und der Rekursentscheid des Statthalteramts des Bezirks Zürich vom 25. April 2007 wird bestätigt.
2. Die Gerichtskosten des bundesgerichtlichen Verfahrens von Fr. 1'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Gerichtskosten des vorinstanzlichen Verfahrens von Fr. 560.-- werden der Beschwerdegegnerin auferlegt.
4. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, und dem Statthalteramt des Bezirks Zürich schriftlich mitgeteilt.
Lausanne, 11. Juni 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Kessler Coendet