Sachverhalt:
A. Mit Vertrag vom 3./8. September 1999 beauftragte die Stadt Y._ X._ für die Dauer von zehn Jahren mit den Abfallsammeldiensten auf dem Stadtgebiet und dem Transport dieser Abfälle zu den von ihr bestimmten Abladeorten. Per 1. Januar 2004 trat eine Vertragsänderung in Kraft, wonach sich einerseits der Abladeort für die Abfälle änderte und sich andererseits - aufgrund des so entstehenden Mehraufwandes für den Transportunternehmer - die finanziellen Abgeltungen erhöhten. Mit Schreiben vom 26. September 2005 und vom 29. November 2005 kündigte der Stadtrat von Y._ den Vertrag mit X._ vorzeitig. Er berief sich dabei auf eine Vertragsbestimmung, wonach eine einseitige Kündigung bei erheblich veränderten Rahmenbedingungen, welche zu einer unzumutbaren finanziellen Übervorteilung einer Partei führen, möglich sei.
B. X._ erachtete die Kündigung des Vertrages als unzulässig und erhob am 10. November 2006 Klage beim Verwaltungsgericht des Kantons Zürich. Darin verlangte er von der Stadt Y._ die Leistung von Schadenersatz in Höhe von Fr. 1'055'198.55 nebst Schadenszins zu 5 % seit dem 1. Mai 2006. Nachdem die Stadt Y._ die Abweisung der Klage beantragt hatte, reduzierte X._ seine Forderung replicando auf Fr. 1'003'936.50. In seinem Urteil vom 10. Juli 2008 erachtete das Verwaltungsgericht die Kündigung des Vertrages durch die Stadt Y._ als rechtens und wies die Klage von X._ vollumfänglich ab.
C. Mit Eingabe vom 19. September 2008 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt die Aufhebung des Urteils des Verwaltungsgerichts und die Rückweisung der Sache an die Vorinstanz.
Die Stadt Y._ beantragt, es sei auf die Beschwerde nicht einzutreten. Eventualiter sei die Beschwerde abzuweisen und der Entscheid des Verwaltungsgerichts vom 10. Juli 2008 vollumfänglich zu bestätigen. Das Verwaltungsgericht des Kantons Zürich beantragt die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid in einer Angelegenheit des öffentlichen Rechts, die unter keinen Ausschlussgrund gemäss <ref-law> fällt und daher mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht weitergezogen werden kann (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Der Beschwerdeführer ist gestützt auf <ref-law> zur Beschwerde in öffentlich-rechtlichen Angelegenheiten legitimiert; auf das frist- und formgerecht eingereichte Rechtsmittel ist daher grundsätzlich einzutreten.
1.2 Mit der Beschwerde kann namentlich die Verletzung von Bundesrecht (einschliesslich der verfassungsmässigen Rechte) gerügt werden (<ref-law>). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.3 Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254).
1.4 Der Beschwerdeführer beantragt die Aufhebung des Urteils des Verwaltungsgerichts und die Rückweisung der Angelegenheit an die Vorinstanz. Er stellt jedoch keinen Antrag zu einem neuen Entscheid in der Sache. Insbesondere beantragt er nicht die Zusprechung von Schadenersatz in bestimmter Höhe. Die Beschwerdegegnerin macht in diesem Zusammenhang geltend, auf die Beschwerde sei nicht einzutreten, weil ein materieller Antrag in der Hauptsache fehle: Bei der Beschwerde in öffentlich-rechtlichen Angelegenheiten handle es sich um ein grundsätzlich reformatorisches Rechtsmittel (<ref-law>), weshalb sich der Beschwerdeführer nicht darauf beschränken dürfte, nur die Aufhebung des angefochtenen Entscheids zu verlangen, wie dies unter der alten Rechtsmittelordnung bei der staatsrechtlichen Beschwerde noch zulässig gewesen sei.
Das Bundesgericht hat in <ref-ruling> E. 1.4.1 entschieden, dass es bezüglich der Beschwerde in öffentlich-rechtlichen Angelegenheiten seine vor Inkrafttreten des BGG begründete Praxis zur Verwaltungsgerichtsbeschwerde beibehalte: In einem Antrag auf Aufhebung des angefochtenen Entscheids sei sowohl die kassatorische als auch die reformatorische Rechtsfolge mitumfasst. Wenn ein Beschwerdeführer auf einen anderslautenden Antrag verzichte, so gebe er damit zu verstehen, dass er die konkreten materiellen Rechtsfolgen der Aufhebung des angefochtenen Entscheids in das Ermessen des Gerichts stelle.
Zwar ist der Einwand der Beschwerdegegnerin grundsätzlich zutreffend, dass im Rahmen der Beschwerde in Zivilsachen die Rechtsprechung zum gleichen Thema strenger ist. Auch nach dieser Praxis würde aber im vorliegenden Fall der Rückweisungsantrag genügen, da das Bundesgericht bei einer Gutheissung der Beschwerde nicht selbst über die Klage entscheiden könnte, zumal die tatsächlichen Feststellungen nicht ausreichen, um über die Höhe des geltend gemachten Schadenersatzes zu befinden (vgl. <ref-ruling> E. 3.1 in fine). Die eingereichte Beschwerde erscheint daher auch unter diesem Aspekt als zulässig.
2. Der Wortlaut von Ziff. 4.6, 4.7 und 5.2 des Vertrages vom 3./8. September 1999 lautet wie folgt:
"4.6 Bei erheblich veränderten Rahmenbedingungen wie
- starke Zu- oder Abnahme der Mengen
- veränderte Transportwege
- veränderte Abfuhrintervalle
- veränderte Abfalltechnologie
- Notstandsmassnahmen
kann jede Partei eine Überprüfung der Entschädigungsregelung verlangen."
"4.7 Weist eine Partei nach, dass die geltende Entschädigungsregelung zu einer unzumutbaren finanziellen Übervorteilung führt, kann sie eine Neuberechnung der Entschädigungsregelung verlangen."
"5.2 Ist einer Vertragspartei aus wichtigen Gründen (wie zum Beispiel Nichtzustandekommen einer Einigung über die Entschädigung, oder trotz schriftlicher Abmahnung andauernde Vertragsverletzungen) das Einhalten dieses Vertrages nachweislich nicht mehr zumutbar, kann sie ihn jederzeit einseitig mit einer sechsmonatigen Frist künden."
3. Das Verwaltungsgericht hat erwogen, dass die Parteien mit diesen Vertragsbestimmungen eine eigene Regelung getroffen hätten, welche - anders als die universell geltende sog. clausula rebus sic stantibus - nicht voraussetze, dass ein Beharren auf der Erfüllung eines Vertrages geradezu als rechtsmissbräuchlich erscheine. Die per 1. Januar 2004 erfolgte Anpassung, bei welcher die Entschädigung für den Beschwerdeführer zufolge eines neuen Abladeortes und veränderten Transportwegen erhöht worden sei, zeige, dass das vertraglich vorgesehene Verfahren bereits bei einer milderen Störung von Leistung und Gegenleistung greife und gegriffen habe. Ein Anspruch auf Anpassung der Entschädigung bestehe mithin dann, wenn eine erhebliche Veränderung der Rahmenbedingungen dazu führe, dass "ein beträchtliches Missverhältnis zwischen Leistung und Gegenleistung" entstehe.
Die Vorinstanz bejahte in der Folge sowohl das Vorliegen von veränderten Rahmenbedingungen als auch das Bestehen eines beträchtlichen Missverhältnisses zwischen der vom Beschwerdeführer erbrachten Leistung und der finanziellen Abgeltung derselben. Das Verwaltungsgericht begründet seine Feststellungen vor allem mit der erheblich erhöhten Wohnbautätigkeit in Y._ in den Jahren 2000-2005. Diese habe sich aufgrund der Koppelung der Abgeltung für den Haushalts- und Gewerbekehricht an die Anzahl Haushalte auf die entrichteten Entschädigungen niedergeschlagen. So hätten die finanziellen Abgeltungen während der Vertragsdauer um 19 % zugenommen. Bei Berücksichtigung des seit dem 1. Januar 2004 zusätzlich ausbezahlten Zuschlags aufgrund des veränderten Abladeortes betrage die Zunahme der entrichteten Entschädigungen für den Haushalts- und Gewerbekehricht gar 27.6 %. Demgegenüber hätten weder die zu transportierende Abfallmenge noch der Fahrweg des Beschwerdeführers signifikant zugenommen. Der in den Büchern des Beschwerdeführers ausgewiesene ordentliche Gesamtaufwand habe sich nur um 7.5 % und der Aufwand für Löhne und Gehälter gar nur um 5.6 % erhöht.
Aus diesem Grund gelangte das Verwaltungsgericht zum Schluss, dass die Stadt Y._ zu Recht die Überprüfung und Neuberechnung der Entschädigungsregelung i.S. der Ziff. 4.6 und 4.7 des Vertrages verlangt habe. Auch seien keine Anhaltspunkte dafür ersichtlich, dass die Stadt Y._ im Zeitpunkt des Vertragsschlusses bereits Kenntnis von den stattfindenden Veränderungen gehabt und deshalb rechtsmissbräuchlich gehandelt habe. Da die Parteien zudem offenkundig ernsthafte und langwierige Verhandlungen über die Neugestaltung des Vertrages geführt hätten und das Angebot des Beschwerdeführers bereits aus submissionsrechtlicher Sicht für die Stadt Y._ unannehmbar gewesen sei, habe Letztere den Vertrag einseitig kündigen dürfen, zumal ihr das Einhalten des Vertrages aufgrund des aufgezeigten Missverhältnisses, der absehbaren weiteren Veränderungen zu ihren Lasten und der restlichen Laufzeit von über dreieinhalb Jahren nicht mehr zumutbar gewesen sei.
4. Der Beschwerdeführer beanstandet die Berechnungen des Verwaltungsgerichts. Er bestreitet das Vorliegen von massgeblich veränderten Rahmenbedingungen und macht im Wesentlichen geltend, bei korrekter Berechnung seiner Leistungen sowie des hierfür entrichteten Entgelts resultiere kein Missverhältnis, welches die Erfüllung des Vertrages durch die Stadt Y._ als unzumutbar erscheinen lasse.
4.1 Der Beschwerdeführer wirft der Vorinstanz insbesondere vor, in ihren Berechnungen selektiv nur auf einzelne Aufwendungen und bezahlte Entschädigungen abzustellen, während Vorteile, welche sich für die Stadt Y._ durch seine Leistung ergeben hätten, ausgeblendet würden; richtigerweise müssten die finanziellen Folgen des gesamten Leistungsaustausches zwischen den Parteien betrachtet werden. In diesem Zusammenhang macht der Beschwerdeführer geltend, dass er im Auftrag der Stadt Y._ nicht nur den Haushalts-, sondern auch den Gewerbekehricht entsorgt habe. In anderen Gemeinden sei dies ein lukratives privates Geschäft der Abfuhrunternehmer, während die Stadt Y._ die entsprechenden Gebühren selbst erhebe und so in den Jahren 2000 bis 2004 einen beträchtlichen Gewinn erzielt habe. In den Berechnungen des Verwaltungsgerichts ebenfalls keine Berücksichtigung gefunden habe, dass die Stadt Y._ aufgrund des erfolgten Wechsels des Abladeortes eine Nettoersparnis von Fr. 72'000.-- pro Jahr habe erzielen können. Sodann sei zu beachten, dass die Stadt Y._ die Container-Preise von Fr. 36.-- auf Fr. 30.-- habe senken können; die Stadt Y._ sei nun aber nicht berechtigt, sich einerseits gegenüber dem Beschwerdeführer auf eine unzumutbare finanzielle Übervorteilung zu berufen, wenn sie andererseits in der Lage sei, die extern verrechneten Tarife für die von ihm erbrachten Leistungen massiv zu senken. Der Beschwerdeführer erkennt in diesen Umständen eine Verletzung des Willkürverbotes von <ref-law> und der Verfahrensgarantien von <ref-law>. Ebenfalls liege eine Missachtung von Art. 2 der Verfassung des Kantons Zürich vom 27. Februar 2005 (KV / ZH) vor, zumal diese Norm u.a. gewährleiste, dass Grundlage und Schranke des staatlichen Handelns das Recht sei.
Die vorgebrachten Argumente vermögen nicht zu überzeugen: Dass die Gebühren für den Gewerbekehricht von der Stadt Y._ erhoben werden, war bereits von Anfang an Teil der Leistungsvereinbarung. Dass sein Aufwand mit dem Gewerbekehricht im Laufe der Vertragsdauer zugenommen hätte, wird vom Beschwerdeführer nicht dargelegt. Es ist demnach nicht ersichtlich, inwiefern sich diese Komponente des Vertrages auf das Verhältnis zwischen erbrachter Leistung und finanziellem Entgelt auswirken sollte. Eine allfällige Ersparnis durch den Wechsel des Abladeortes kann sich der Beschwerdeführer ebenfalls nicht zurechnen lassen: Diese hängt nur insoweit mit der von ihm erbrachten Leistung zusammen, als er einen längeren Transportweg bewältigen muss. Für diesen Mehraufwand wurde der Beschwerdeführer seit dem 1. Januar 2004 aber separat mit zusätzlichen Fr. 11.--/Tonne entschädigt, so dass das Preis-/Leistungsgleichgewicht auch durch diesen Aspekt nicht berührt wird. Nichts anderes gilt bezüglich der monierten Senkung der Container-Preise: Diese betreffen ausschliesslich das Verhältnis zwischen der Stadt Y._ und ihren Kunden und haben keine Auswirkungen auf den Aufwand des Beschwerdeführers oder die zu entrichtende Entschädigung. Nach dem Gesagten ist ein willkürliches Vorgehen der Vorinstanz jedenfalls ebensowenig zu erkennen wie die behauptete Verletzung von <ref-law>. Dem ebenfalls angerufenen Art. 2 KV / ZH kommt keine eigenständige Bedeutung zu, zumal sich der vom Beschwerdeführer angerufene Grundsatz der Gesetzmässigkeit des staatlichen Handelns (Legalitätsprinzip) in identischer Form auch in <ref-law> findet. Eine Verletzung dieses Grundsatzes liegt aufgrund der genannten Gründe aber klarerweise nicht vor.
4.2 Weiter macht der Beschwerdeführer geltend, er habe die durch die leistungsabhängige Schwerverkehrsabgabe (LSVA) verursachte Teuerung nie auf die Stadt Y._ überwälzt, obwohl ihm Anhang 2 des Vertrages dies gestattet hätte. Dies sei bei der Frage, ob eine erhebliche Veränderung der Rahmenbedingungen vorliege, mitzuberücksichtigen. In diesem Zusammenhang rügt der Beschwerdeführer ebenfalls, dass die Vorinstanz hinsichtlich der Veränderung der bezahlten Entschädigungen auf unbereinigte Zahlen abgestellt habe: Da die Überwälzung der durch die LSVA bedingten Teuerung vertraglich vereinbart gewesen sei, habe die Stadt Y._ zumindest mit Kostensteigerungen in diesem Umfang rechnen müssen; insoweit liege mithin eine bereits im ursprünglichen Vertrag vorgesehene Erhöhung der Entschädigung vor, welche nicht als veränderter Umstand bezeichnet werden könne. Daher müsse zur korrekten Berechnung der Netto-Veränderung der Entschädigungen nicht nur - wie dies das Verwaltungsgericht getan habe - der buchhalterisch ausgewiesene Mehraufwand des Beschwerdeführers von der festgestellten Erhöhung der Entschädigung abgezogen werden, sondern eben auch die vertraglich vereinbarte Teuerung. Im Zusammenhang mit diesen Rügen behauptet der Beschwerdeführer erneut die Verletzung von Art. 9 und <ref-law>.
Im vorliegenden Fall kann offen bleiben, ob und in welchem Umfang die Teuerung vom Beschwerdeführer überwälzt wurde und inwiefern die von ihm erhobenen Rügen unter dem Gesichtspunkt des Novenverbotes von <ref-law> (vgl. E. 1.2) überhaupt zulässig sind: Die vorgebrachten Einwände halten einer Prüfung nicht stand. Zwar mag es zutreffen, dass die Stadt Y._ beim Abschluss des Vertrages mit Kostensteigerungen im Rahmen der Teuerung rechnen musste. Es ist aber unbestritten, dass die Erhöhung der von der Stadt Y._ an den Beschwerdeführer entrichteten Entgelte nicht auf die Teuerung, sondern auf andere Faktoren, namentlich die Erhöhung des Wohnraumbestandes und die Koppelung der geschuldeten Entschädigung an die Anzahl der bestehenden Haushalte zurückzuführen ist. Wenn der Beschwerdeführer geltend macht, dass er die Teuerung sozusagen aus Kulanz nicht auf die Stadt Y._ überwälzt habe, ändert dies bereits deshalb nichts, weil sich die diesfalls von ihm getragenen Mehrkosten in seiner Erfolgsrechnung niedergeschlagen haben müssen und auf diese Weise in die Berechnungen der Vorinstanz eingeflossen sind.
4.3 Sodann rügt der Beschwerdeführer, bei der Beurteilung von "erheblich veränderten Rahmenbedingungen" bzw. einem "angeblich neu entstandenen beträchtlichen Missverhältnis zwischen den ausgetauschten Leistungen" dürfe auch die seit dem 1. Januar 2004 aufgrund des geänderten Abladeortes entrichtete zusätzliche Vergütung von Fr. 11.-- /Tonne nicht als Veränderung berücksichtigt werden. Was man im Zeitpunkt des Vertragsschlusses bereits vereinbart habe, könne später nicht als unvorhersehbare Veränderung geltend gemacht werden. Der Beschwerdeführer sieht auch insofern das Willkürverbot verletzt.
Den Argumenten des Beschwerdeführers kann erneut nicht gefolgt werden: Einerseits hat die Vorinstanz willkürfrei festgestellt, dass gemäss den vertraglichen Bestimmungen die Unvorhersehbarkeit einer Veränderung keine Voraussetzung für das Recht beider Parteien sei, eine Überprüfung der Entschädigungsregelung zu verlangen. Andererseits hat das Verwaltungsgericht den betreffenden Zuschlag separat ausgewiesen und die Kostensteigerung für die Stadt Y._ jeweils mit und ohne Zuschlag errechnet. Die Vorinstanz gelangte indes zum Ergebnis, dass selbst mit der für den Beschwerdeführer günstigsten Betrachtungsweise eine erhebliche Veränderung der Rahmenbedingungen und das Vorliegen eines beträchtlichen Missverhältnisses zwischen Leistung und Gegenleistung bejaht werden müsse. Die vom Beschwerdeführer erhobene Rüge zielt somit ins Leere.
4.4 Vom Beschwerdeführer wird zudem beanstandet, dass die Vorinstanz die Zunahme der Wohnbautätigkeit in der Stadt Y._ anhand der Zahlen der Jahre 1999 bis 2005 errechnet habe, obwohl der Beschwerdeführer und die Stadt Y._ darin übereingestimmt hätten, dass die Zahlen der Jahre 2000 bis 2004 zu vergleichen seien: Es verstosse gegen anerkannte Prozessregeln, insbesondere die Dispositionsmaxime, wenn das Verwaltungsgericht einen Sachverhalt zu einer entscheidenden Feststellung im Urteil mache, der von den Parteien im Kern wesentlich anders dargestellt worden sei. Die Vorgehensweise des Verwaltungsgerichts sei daher willkürlich und verstosse zudem gegen Art. 2 KV / ZH.
Inwiefern der Einwand des Beschwerdeführers den Bereich der Dispositionsmaxime betreffen soll, ist nicht ersichtlich. Jedenfalls ist diese hier nicht verletzt worden, zumal das Verwaltungsgericht nicht über die Anträge der Parteien hinausgegangen ist. Der Einwand geht jedoch auch insoweit fehl, als er auf die Verhandlungsmaxime abzielt. Diese gilt im öffentlichen Prozessrecht nur in beschränktem Umfang und wird zumeist durch die Untersuchungsmaxime ersetzt (vgl. § 7 Abs. 1 und § 60 i.V. mit Art. 86 VRG). Im vorliegenden Fall ging es der Vorinstanz offenkundig darum, einerseits die Veränderung der Anzahl Haushalte während der bisherigen Vertragslaufzeit zu eruieren und andererseits aufgrund dieser Zahlen einen Trend bezüglich der zukünftigen Entwicklung abzuleiten (vgl. E. 5.2.2 und 5.2.3 des angefochtenen Entscheids). Dass das Verwaltungsgericht zu diesem Zweck sämtliche verfügbaren Daten beigezogen hat, welche die fragliche Zeitperiode betreffen, erscheint nicht nur nachvollziehbar, sondern geradezu geboten. Die Vorinstanz ist daher weder in Willkür verfallen, noch hat sie Art. 2 KV / ZH verletzt (vgl. hierzu E. 4.1).
4.5 Gerügt wird ferner, dass das Verwaltungsgericht zur Feststellung gelangt sei, der buchhalterisch ausgewiesene Betriebsaufwand des Beschwerdeführers sei während der Vertragsdauer nur minimal gestiegen, ohne dass es aber in hinreichendem Mass berücksichtigt habe, dass dieser Umstand auch auf eine erhöhte und verbesserte Produktivität des Unternehmers zurückzuführen sei. Die Vorinstanz habe "keine Ahnung über einen allfällig rigoros verbesserten Einkauf von Waren und Material, eine effizientere Unterhaltung des Wagenparks, allfällige Einsparungen von Personalkosten dadurch, dass der Unternehmer selber ein Mehr an Stunden arbeite als seine Mitarbeitenden, etc.". Die Feststellung, dass der Betriebsaufwand nur minimal gestiegen sei, müsse daher als willkürliche Sachverhaltsfeststellung bzw. als Willkür und grobes Unrecht taxiert werden.
Dem Einwand ist entgegenzuhalten, dass die Vorinstanz in E. 5.3.3 des angefochtenen Entscheides ausdrücklich festgehalten hat, dass "eine verhältnismässig geringe Aufwandsteigerung in der Rechnung des Klägers auch auf eine verbesserte Arbeitsweise zurückgeführt werden kann, welche ihm als Unternehmer zu Gute kommen muss (...) und damit nicht notwendigerweise den gesamten zusätzlichen Aufwand widerspiegelt". Das Verwaltungsgericht bringt damit zum Ausdruck, dass es den Aspekt der Produktivitätssteigerung erkannt hat, und diesen, mangels genauerer Bezifferbarkeit, bei seiner Beurteilung in angemessenem Umfang mitberücksichtigt hat. Dieses Vorgehen ist unter Willkürgesichtspunkten nicht zu beanstanden. Wenn der Beschwerdeführer geltend machen wollte, dass die Effizienzsteigerung in seinem Betrieb noch weitergehende Auswirkungen auf die Eindämmung der Kostensteigerung gehabt habe, wäre es an ihm gewesen, dies substantiiert aufzuzeigen und zu belegen: Nur er verfügt über das diesbezügliche Wissen und die entsprechenden Unterlagen. Durch den pauschalen Verweis auf "allfällig" getroffene Massnahmen wird er seiner qualifizierten Begründungspflicht (Art. 42 Abs. 2 und <ref-law>; vgl. E. 1.3) jedenfalls nicht gerecht, so dass auf die Beschwerde in diesem Punkt nicht einzutreten ist.
4.6 Der Beschwerdeführer meint schliesslich in allgemeiner Weise, dass es den verfassungsmässigen Anspruch auf rechtliches Gehör verletze, wenn die Vorinstanz auf Sachverhaltsfeststellungen abgestellt habe, welche von den Parteien nicht akzeptiert worden seien: Hätte es solche Feststellungen zur Entscheidungsgrundlage erheben wollen, wäre es unabdingbar gewesen, dies vorgängig anzuzeigen. Auch diese Rüge erweist sich bereits unter dem Gesichtspunkt der Substantiierungslast von Art. 42 Abs. 2 i.V.m. <ref-law> als unzulässig: Den Akten sowie dem angefochtenen Entscheid kann entnommen werden, dass im verwaltungsgerichtlichen Verfahren ein doppelter Schriftenwechsel durchgeführt wurde. Der Beschwerdeführer hat es versäumt, präzise darzulegen, bezüglich welcher Punkte die Vorinstanz auf Sachumstände abgestellt haben soll, zu welchen er noch nie hat Stellung nehmen können.
5. Die Beschwerde erweist sich demzufolge als unbegründet und ist abzuweisen, soweit darauf einzutreten ist.
Entsprechend diesem Verfahrensausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (Art. 65 f. BGG). Eine Parteientschädigung ist ihm nicht auszurichten (<ref-law>). Die Beschwerdegegnerin hat als Gemeinde, welche in ihrem amtlichen Wirkungsbereich prozessierte, grundsätzlich keinen Anspruch auf eine Parteientschädigung (<ref-law>). Das vorliegende Verfahren ist nicht von derart besonderer Natur, dass vom Grundsatz der Entschädigungslosigkeit abzuweichen wäre, wie dies die Beschwerdegegnerin beantragt.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 20'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Beschwerdegegnerin und dem Verwaltungsgericht des Kantons Zürich, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 6. März 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler