Sachverhalt:
A. Die Corvatsch Power GmbH, welche bis anhin bereits mit dem Sammeldienst für den Hauskehricht im Gebiet des Abfallbewirtschaftungsverbands Oberengadin-Bergell (exklusive St. Moritz und Bergell) betraut war, erhielt am 16. Februar 2006 aufgrund einer neuen Submission auch den Zuschlag für die Zeitspanne vom 1. Juni 2006 bis 31. Mai 2011. Hiergegen beschwerte sich ein Mitbewerber beim Verwaltungsgericht des Kantons Graubünden, worauf der Abfallbewirtschaftungsverband - im Sinne einer Übergangslösung - die Corvatsch Power GmbH mit der Weiterführung des Sammeldienstes ab dem 1. Juni 2006 bis zum Abschluss des Rechtsmittelverfahrens beauftragte.
B. Nachdem das Verwaltungsgericht des Kantons Graubünden die Beschwerde des Mitbewerbers am 8. Mai 2006 abgewiesen hatte, stellte der Abfallbewirtschaftungsverband der Corvatsch Power GmbH den Vertrag für die künftige Besorgung des Sammeldienstes zur Unterzeichnung zu. Die Corvatsch Power GmbH beanstandete jedoch, die (bereits in der Ausschreibung angegebene) jährliche Abfallmenge von rund 4'366 Tonnen, nach welcher sich ihre Entschädigung richten sollte, sei zu hoch; der tatsächliche Durchschnitt der vergangenen Jahre liege bei 4'181 Tonnen. Sie verlangte deshalb einen Ausgleich des sich aus der fraglichen Differenz ergebenden Ertragsausfalls. Nachdem eine Besprechung zu keinem Ergebnis geführt hatte, lehnte der Verband die beantragte Vertragsanpassung mit Schreiben vom 25. Juli 2006 definitiv ab; gleichzeitig stellte er fest, dass die (mündlich) vereinbarte Verlängerung des bisherigen Vertrags infolge des Scheiterns der Verhandlungen über den Abschluss eines neuen Vertrags am 31. Juli 2006 ende. Am 27. Juli 2006 teilte der Verband den beteiligten Gemeinden und den Bewerbern mit, dass ab 1. August 2006 das im Submissionsverfahren zweitplatzierte Unternehmen den Sammeldienst übernehmen werde. Tags darauf sandte die Corvatsch Power GmbH dem Verband den unterzeichneten Vertrag zurück und erklärte, sie verzichte auf die bisher geforderte Anpassung der jährlichen Abfallmenge. Der Verband erklärte die Vertragsunterzeichnung jedoch für verspätet und hielt an der Beauftragung des zweitplatzierten Mitbewerbers fest (Schreiben vom 31. Juli 2006).
C. Am 25. August 2006 beschwerte sich die Corvatsch Power GmbH beim Verwaltungsgericht des Kantons Graubünden und verlangte, dass der Abfallbewirtschaftungsverband Oberengadin-Bergell zum Abschluss des ihr am 26. Mai 2006 unterbreiteten Vertrags verpflichtet werde, wobei - für den Fall einer Unterschreitung der in der Ausschreibung angegebenen Abfallmengen - eine Anpassung des Tonnenpreises vorzusehen sei. Das Verwaltungsgericht erklärte sich für unzuständig, über das Zustandekommen des Vertrags zu urteilen, und verwies die Corvatsch Power GmbH insoweit an die Zivilgerichte. Weil es die vorläufige Beauftragung eines Drittunternehmers mit der Abfallentsorgung als rechtmässig beurteilte, wies es die Beschwerde im Übrigen ab (Urteil vom 7. November 2006). Diesen Entscheid schützte das Bundesgericht auf staatsrechtliche Beschwerde hin (Urteil 2P.329/2006 vom 15. Juni 2007).
D. In der Folge gelangte die Corvatsch Power GmbH an das Bezirksgericht Maloja, dem sie zur Hauptsache die gleichen Anträge unterbreitete wie dem Verwaltungsgericht; zusätzlich verlangte sie noch Schadenersatz in der Höhe von 100'000 bzw. 500'000 Franken. Das Bezirksgericht wies die Klage am 13. November 2007 ab, soweit es darauf eintrat: Es erachtete sowohl den abzuschliessenden Vertrag als auch die gestellte Schadenersatzforderung als öffentlichrechtlicher Natur und hielt sich deshalb für sachlich unzuständig. In einer Eventualbegründung erklärte es die Klage zudem für unbegründet, weil einerseits keine Kontrahierungspflicht bestehe und andererseits kein Konsens vorliege.
E. Diesen Entscheid focht die Corvatsch Power GmbH beim Kantonsgericht von Graubünden an, wobei sie grundsätzlich die gleichen Anträge wie im erstinstanzlichen Verfahren stellte, aber ihre Schadenersatzforderung auf 13'463.65 Franken reduzierte. Im Unterschied zum Bezirksgericht qualifizierte das Kantonsgericht den abzuschliessenden Vertrag als privatrechtlicher Natur und, aufgrund übereinstimmender Willenserklärungen, als zustande gekommen. Es hiess mit Urteil vom 11. März 2008 die Berufung teilweise gut, hob das Urteil des Bezirksgerichts auf (Ziff. 1) und verpflichtete den Abfallbewirtschaftungsverband Oberengadin-Bergell - obschon es in den Erwägungen vom Zustandekommen des Vertrags ausgegangen war - zum Vertragsschluss mit der Corvatsch Power GmbH (Ziff. 2a); dieser sprach sie gleichzeitig Schadenersatz in der Höhe von 10'800 Franken zu (Ziff. 2b).
F. Am 13. Juni 2008 hat der Abfallbewirtschaftungsverband Oberengadin-Bergell beim Bundesgericht Beschwerde in Zivilsachen eingereicht mit dem Antrag, den angefochtenen Entscheid aufzuheben und die Klage der Corvatsch Power GmbH abzuweisen, soweit darauf einzutreten sei; eventuell sei die Sache zur Neubeurteilung an das Kantonsgericht von Graubünden zurückzuweisen. Er rügt insbesondere eine Verletzung von Bundesrecht, weil das Kantonsgericht zu Unrecht Privatrecht an Stelle von kantonalem Verwaltungsrecht angewandt habe.
Die Corvatsch Power GmbH schliesst auf Abweisung der Beschwerde, während das Kantonsgericht von Graubünden beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei.
G. Mit Verfügung vom 18. Juli 2008 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zuerkannt.
Erwägungen:
1. Der Beschwerdeführer hat - der Rechtsmittelbelehrung im kantonalen Urteil entsprechend - beim Bundesgericht Beschwerde in Zivilsachen erhoben. Für die Behandlung dieses Rechtsmittels sind grundsätzlich die beiden Zivilabteilungen zuständig (vgl. Art. 31 f. des Reglements vom 20. November 2006 für das Bundesgericht; SR 173.110.131). Gemäss Art. 36 des Reglements ist für die Zuteilung eines Geschäfts die Rechtsfrage massgebend, auf der das Schwergewicht der Entscheidung liegt (Abs. 1), wobei im Einzelfall von der reglementarisch vorgesehenen Geschäftsverteilung abgewichen werden kann, wenn dies die Natur des Geschäfts oder dessen Konnexität mit anderen Verfahren nahelegt. In Anwendung dieser Grundsätze hat die II. öffentlich-rechtliche Abteilung das vorliegende Verfahren übernommen, obschon sie ansonsten ausschliesslich Beschwerden in öffentlich-rechtlichen Angelegenheiten und subsidiäre Verfassungsbeschwerden aus den ihr zugewiesenen Sachgebieten beurteilt (vgl. Art. 30 des Reglements). Ausschlaggebend hiefür ist, dass die sich vorliegend stellenden Rechtsfragen in engem Zusammenhang mit dem Vergabeverfahren stehen, welches dem umstrittenen Vertragsschluss vorangegangen ist und das seinerseits bereits Gegenstand eines von der II. öffentlich-rechtlichen Abteilung behandelten Rechtsmittelverfahrens bildete (vgl. Sachverhalt lit. C).
2. Der Beschwerdeführer macht vorab geltend, das Kantonsgericht habe das Zustandekommen des Vertrags zu Unrecht gestützt auf Bundeszivilrecht beurteilt bzw. fälschlicherweise nicht das kantonale öffentliche Recht angewandt. Daraus schliesst er, die Vorinstanz sei zur Beurteilung der Streitsache gar nicht zuständig gewesen.
2.1 Über das Mittel der öffentlichen Beschaffung soll einerseits das Gemeinwesen die benötigten Sachen und Dienstleistungen wirtschaftlich günstig einkaufen können und andererseits die Gleichbehandlung der Anbieter sowie die Transparenz des Auswahlverfahrens sichergestellt werden. Die Verfügung, in welche die Submission mündet, bestimmt verbindlich, mit welchem Bewerber die Vergabebehörde einen Vertrag schliessen soll, "vergibt" aber den Gegenstand des Vergabeverfahrens nicht unmittelbar an den ausgewählten Anbieter. Mit diesem hat das Gemeinwesen nach dem Zuschlag einen Vertrag abzuschliessen über die Erbringung der benötigten Dienstleistung bzw. die Lieferung der nachgesuchten Waren. Anders als im vorangehenden Vergabeverfahren, in dem die zuständige Behörde hoheitlich handelt, treten sich der Anbieter und das Gemeinwesen dabei in der Regel auf dem Boden des Privatrechts gegenüber und schliessen einen privatrechtlichen Vertrag ab (sog. Zweistufentheorie; vgl. Peter Galli/André Moser/Elisbeth Lang/Evelyne Clerc, Praxis des öffentlichen Beschaffungsrechts, 2. Auflage, Zürich 2007, N 701; Ulrich Häfelin/Georg Müller/Felix Uhlmann, Allgemeines Verwaltungsrecht, 5. Auflage, Zürich 2006, N 287 f.).
2.2 Je nach Inhalt kann die vom Zuschlagsempfänger zu erbringende Leistung aber auch Gegenstand einer öffentlich-rechtlichen Vereinbarung bilden. Es ist im konkreten Fall zu prüfen, ob ein vom Gemeinwesen geschlossener Vertrag verwaltungsrechtlicher oder privatrechtlicher Natur ist, was sich vorab nach dem Gegenstand der durch ihn begründeten Rechte und Pflichten beurteilt: Ein verwaltungsrechtlicher Vertrag hat direkt die Erfüllung einer öffentlichen Aufgabe zum Inhalt oder betrifft einen im öffentlichen Recht geregelten Gegenstand, zum Beispiel eine Erschliessung, Enteignung oder Subvention (BGE 128 III 250 E. 2b S. 253 f.; vgl. auch René Rhinow, Verfügung, Verwaltungsvertrag und privatrechtlicher Vertrag, in: Festgabe zum Schweizerischen Juristentag 1985, S. 303; Häfelin/Müller/Uhlmann, a.a.O., N 1058). Demgegenüber liegt eine privatrechtliche Vereinbarung vor, wenn sich der Staat durch Kauf, Werkvertrag oder Auftrag bloss die Hilfsmittel beschafft, derer er zur Erfüllung seiner öffentlichen Aufgaben bedarf. Allerdings kann die Zuordnung eines Vertrags zum einen oder anderen Rechtsbereich im konkreten Einzelfall mit Schwierigkeiten verbunden sein, so dass gegebenenfalls beide Betrachtungsweisen zulässig erscheinen.
3. Nach dem Gesagten ist zunächst die Rechtsnatur des Gegenstand der Ausschreibung bildenden Vertrags zu bestimmen.
3.1 Die Entsorgung von Siedlungsabfällen ist Sache der Kantone (vgl. Art. 31b des Bundesgesetzes vom 7. Oktober 1983 über den Umweltschutz [USG; SR 814.01]), welche diese Aufgabe jedoch delegieren können (Art. 43 USG; vgl. auch BGE 123 II 359 E. 5a S. 367). Dementsprechend hat der Kanton Graubünden die Entsorgung der Siedlungsabfälle den Gemeinden übertragen, welche gemäss Art. 35 Abs. 2 des Bündner Einführungsgesetzes zum Bundesgesetz über den Umweltschutz (KUSG) insbesondere zuständig sind für den Bau und Betrieb der notwendigen Abfallanlagen (lit. b), die Sammlung der Siedlungsabfälle und deren Transport zu den Abfallanlagen (lit. a) sowie die Einrichtung von Sammelstellen für kleinere Mengen von Sonderabfällen aus Haushalt und Kleingewerbe (lit. c). Der Kanton hat den Gemeinden dabei ausdrücklich gestattet, diese Aufgaben öffentlich-rechtlichen Körperschaften oder geeigneten privaten Unternehmen weiter zu übertragen (Art. 35 Abs. 3 KUSG). So haben sich die Gemeinden des Oberengadins zu einem Gemeindeverband - dem Beschwerdeführer - zusammengeschlossen, der nun seinerseits einen Teil jener Aufgaben, welche der kantonale Gesetzgeber im Bereich der Abfallentsorgung den Gemeinden und diese ihm überbunden haben, auf ein privates Transportunternehmen übertragen will.
3.2 Im angefochtenen Entscheid hat das Kantonsgericht erwogen, der Beschwerdeführer gedenke bloss einen Teil seiner Verpflichtung zur Abfallentsorgung einem privaten Unternehmer zu überbinden, betreffe der streitige Vertrag doch nur den Sammel- und Transportdienst in einem Teil der Verbandsgemeinden. Dem privaten Vertragspartner werde so nicht die öffentliche Aufgabe als solche übertragen, zumal die Verantwortlichkeit für Abfuhr, Verwertung und Entsorgung von Hauskehricht beim Beschwerdeführer verbleibe. Vertragsgegenstand bilde bloss "die Sammel- und Transportdienstleistung als reine Hilfstätigkeit", so dass es um den Abschluss eines privatrechtlichen und nicht eines verwaltungsrechtlichen Vertrags gehe.
3.3 Dem lässt sich entgegenhalten, dass der Abtransport des Hauskehrichts schon für sich allein als eigentliche öffentliche Aufgabe betrachtet werden kann und - entgegen den Ausführungen der Vorinstanz - nicht bloss eine untergeordnete Hilfstätigkeit zur Abfallentsorgung als Ganzes darzustellen braucht; es verhält sich diesbezüglich anders, als wenn etwa die blosse Beschaffung der für die Kehrichtabfuhr benötigten Fahrzeuge in Frage stünde. Dem Beschwerdeführer ist deshalb insoweit Recht zu geben, als die streitbetroffene Dienstleistung durchaus Gegenstand eines öffentlich-rechtlichen Vertrags bilden könnte (wie das offenbar im Kanton Zürich der Fall ist). Allerdings ist diese rechtliche Einordnung mit Blick darauf, dass einerseits die Abgrenzung zwischen der Übertragung einer eigentlichen öffentlichen Aufgabe und einer blossen Hilfstätigkeit fliessend ist und anderseits auch die von der öffentlichen Hand abgeschlossenen Verträge im Zweifelsfall privatrechtlicher Natur sind, in einem Fall wie dem vorliegenden nicht zwingend; der zuständige Gesetzgeber hat es in der Hand, die Rechtsnatur solcher Verträge festzulegen (vgl. Häfelin/ Müller/Uhlmann, a.a.O., N 1057). Hier hat sich der Kanton Graubünden darauf beschränkt, in Art. 35 Abs. 3 KUSG klarzustellen, dass die Gemeinden auch im Bereich der Abfallentsorgung auf private Dienstleister zurückgreifen können. Eine rechtliche Zuordnung derartiger Vereinbarungen mit privaten Unternehmern hat er in den einschlägigen Bestimmungen nicht vorgenommen. Aus dem vorliegenden Vertragsentwurf, der verschiedentlich auf Artikel des Obligationenrechts verweist und zudem eine Gerichtsstandsklausel enthält, ist aber ersichtlich, dass die Parteien selber ursprünglich von einem privatrechtlichen Vertrag ausgegangen sind und nicht eine verwaltungsrechtliche Vereinbarung schliessen wollten. Zudem haben auch das Verwaltungsgericht als oberste kantonale Instanz im Bereich des öffentlichen Rechts und die Vorinstanz als oberstes kantonales Zivilgericht den Vertrag übereinstimmend als privatrechtlich qualifiziert. Diese Einschätzung ist bundesrechtlich nicht zu beanstanden, zumal die streitbetroffene Vereinbarung die Einzelheiten der zu erbringenden Dienstleistung detailliert regelt und der Beschwerdegegnerin relativ wenig Gestaltungsspielraum lässt, womit die vorgenommene Einordnung als (blosse) Hilfeleistung bei der Aufgabenerfüllung durch den Beschwerdeführer zulässig erscheint.
3.4 Aus dem Gesagten erhellt, dass der streitbetroffene Vertrag ohne Verletzung von Bundesrecht im Sinne von Art. 95 lit. a BGG als privatrechtlich betrachtet werden kann, und die Vorinstanz deshalb zur Beurteilung der vorliegenden Streitigkeit berufen war; die Beschwerde ist insoweit unbegründet.
4. Der Beschwerdeführer bestreitet weiter, dass zwischen ihm und der Beschwerdegegnerin ein Vertrag zustande gekommen ist bzw. dass er zum Abschluss eines solchen verpflichtet werden kann.
4.1 Der Zuschlag begründet noch keine Kontrahierungspflicht des Submittenten (BGE 129 I 410 E. 3.4 S. 416). Deshalb kann sich, ungeachtet der Formulierung des Dispositivs des angefochtenen Entscheids (vgl. Sachverhalt lit. E), in materieller Hinsicht zum Vornherein nur fragen, ob der streitbetroffene Vertrag mit der Beschwerdegegnerin - entgegen der Auffassung des Beschwerdeführers - zustande gekommen ist. Diese Rechtsfrage wurde durch das Verwaltungsgericht, welches vor dem Kantonsgericht mit der vorliegenden Streitigkeit befasst war, noch nicht verbindlich beantwortet, weil es aufgrund der zivilrechtlichen Natur des Verfahrensgegenstands in seinem Urteil vom 7. November 2006 insoweit auf das Rechtsmittel der Beschwerdegegnerin nicht eingetreten ist. Dass es im Zusammenhang mit seinem Entscheid, die vorläufige Beauftragung des im Vergabeverfahren zweitplatzierten Unternehmens sei rechtskonform gewesen, einen Vertragsschluss zwischen dem Beschwerdeführer und der Beschwerdegegnerin klar verneinte (vgl. das betreffende Urteil auf S. 7 f., E. 4b), ändert nichts. Da das Zustandekommen des Vertrags für den betreffenden Entscheid eine blosse Vorfrage bildete, liegt insoweit keine res iudicata vor.
4.2 Zwar müssen im Zeitpunkt der Zuschlagserteilung bereits alle wesentlichen Elemente des künftigen Vertrags feststehen (vgl. Galli/ Moser/Lang/Clerc, a.a.O., N 702). Entgegen der Auffassung des Kantonsgerichts stellen die von den verschiedenen Bewerbern im Submissionsverfahren eingereichten Angebote aber technisch noch keine Offerten zum Vertragsschluss dar. Vielmehr beginnen die Vertragsverhandlungen zwischen Vergabebehörde und Zuschlagsempfänger erst nach Abschluss des Vergabeverfahrens, können sich die Vertragspartner doch - selbst wenn bezüglich der Essentialia des Vertrags keine Abweichungen von Ausschreibungsunterlagen und ausgewähltem Angebot mehr zulässig sind (vgl. Galli/Moser/Lang/Clerc, a.a.O., N 702) - über blosse Nebenpunkte noch frei verständigen. Mithin haben auf den Zuschlag, wie bei einem vom Submissionsverfahren unabhängigen Vertragsschluss, Offerte und Akzept zu folgen.
4.3 Vorliegend hat der Beschwerdeführer der Beschwerdegegnerin am 26. Mai 2006, in der Form eines schriftlichen Vertragsentwurfs, eine solche Offerte unterbreitet. Obschon diese sowohl den Ausschreibungsunterlagen als auch dem von der Beschwerdegegnerin eingereichten Angebot entsprach, hat Letztere den Vertrag nicht unterzeichnet, sondern bezüglich ihrer Entschädigung eine Vertragsänderung verlangt. In der Folge wurde sie vergeblich darauf aufmerksam gemacht, dass es der Vergabebehörde untersagt ist, nach dem Zuschlag noch über wesentliche Vertragselemente zu verhandeln (vgl. oben). Die Beschwerdegegnerin beharrte auf einer zusätzlichen Entschädigung für den Fall, dass die Menge des tatsächlich abgeführten Abfalls geringer sei als die in den Ausschreibungsunterlagen erwähnten 4'366 Tonnen. Zwar unterzeichnete sie den ihr zugestellten Vertrag schliesslich am 28. Juli 2006 doch noch; entgegen der Auffassung der Vorinstanz erfolgte dieses Akzept jedoch nicht mehr rechtzeitig:
4.3.1 Eine unbefristete Offerte bindet den Antragsteller grundsätzlich bis zu jenem Zeitpunkt, in dem er den Eingang der Antwort bei deren ordnungsgemässer Absendung erwarten darf (vgl. Art. 5 OR), wobei dem Empfänger eine angemessene Überlegungsfrist zusteht, deren Dauer sich im konkreten Fall nach der Art des Geschäfts richtet (vgl. BGE 98 II 109 E. 2b S. 111). Vorliegend darf von einer relativ kurzen Bedenkfrist für die Beschwerdegegnerin ausgegangen werden, zumal alle Essentialia der Vereinbarung bereits durch die öffentliche Ausschreibung und das daraufhin eingereichte Angebot bestimmt waren. Es erscheint jedenfalls ausgeschlossen, dass der Beschwerdeführer insgesamt mehr als zwei Monate an seine Offerte gebunden gewesen wäre. Er brachte denn auch im Schreiben vom 25. Juli 2006 klar zum Ausdruck, dass er selber sich spätestens in diesem Moment nicht mehr gebunden sah. Die Beschwerdegegnerin konnte den Vertrag deshalb durch ihre Vertragsunterzeichnung bzw. Annahmeerklärung vom 28. Juli 2006 nicht mehr zum Abschluss bringen.
4.3.2 Hinzu kommt, dass die Beschwerdegegnerin zuvor mit Schreiben vom 12. Juli 2008 einen höheren Tonnenpreis (für den Falle eines Unterschreitens der Abfallmenge gemäss Ausschreibungsunterlagen) und mithin eine Anpassung bezüglich eines der Essentialia des Vertrags verlangt hatte. Dabei führte sie zur Begründung aus, ansonsten "laufe sie unberechtigterweise in den Verlust". Entgegen den Erwägungen der Vorinstanz lässt sich dieses Schreiben nur im Sinne einer Ablehnung der Offerte des Beschwerdeführers verstehen, zumal die Beschwerdegegnerin darin klar zum Ausdruck bringt, kein (vermeintliches) Verlustgeschäft abschliessen zu wollen. Diese Ablehnung - unter gleichzeitiger Unterbreitung einer angepassten, eigenen Vertragsofferte - liess die Bindungswirkung der Offerte des Beschwerdeführers dahinfallen, sollte zu diesem Zeitpunkt überhaupt noch eine solche bestanden haben. Mit Schreiben vom 25. Juli 2006 lehnte der Beschwerdeführer in der Folge seinerseits die Offerte der Beschwerdegegnerin ab. Dass Letztere gar nie ernsthaft zur Annahme der Vertragsofferte des Beschwerdeführers bereit war, zeigt im Übrigen auch ihr späteres Verhalten: So berief sich die Beschwerdegegnerin einerseits zwar auf das Zustandekommen des Vertrags, verlangte aber andererseits sowohl im Verfahren vor dem Verwaltungsgericht als auch später vor den Zivilgerichten stets weiterhin eine höhere Entschädigung mittels Anpassung des Tonnenpreises. Ferner hatte sie sich überhaupt erst dann zur (verspäteten) Vertragsunterzeichnung entschlossen, als sich das definitive Scheitern des Geschäfts abzeichnete, weil der Beschwerdeführer die mündlich vereinbarte Auftragsverlängerung gekündigt und zudem ab August 2006 (vorübergehend) eine Konkurrentin der Beschwerdegegnerin mit der Kehrichtabfuhr beauftragt hatte (vgl. Sachverhalt lit. B).
4.4 Nach dem Gesagten steht fest, dass zwischen den Parteien kein Vertrag zustande gekommen ist; dies bedeutet jedoch nicht, dass der Beschwerdeführer im Entscheid frei wäre, wen er künftig mit der Kehrichtabfuhr in den Verbandsgemeinden betrauen möchte. Solange der Zuschlag an die Beschwerdegegnerin noch Bestand hat, darf er mit keinem anderen Unternehmen über den Gegenstand des Vergabeverfahrens einen Vertrag schliessen (BGE 134 II 192 E. 1.4 S. 196). Bei der veranlassten Beauftragung der Konkurrentin der Beschwerdegegnerin kann es sich zum Vornherein nur um eine provisorische Übergangslösung handeln, bis der Rechtsstreit zwischen den Parteien beendet ist. Will der Beschwerdeführer anschliessend den Auftrag nicht mehr der Beschwerdegegnerin, sondern einem Dritten erteilen, hat er seinen Zuschlagsentscheid förmlich zu widerrufen (und allenfalls das ganze Vergebungsverfahren zu wiederholen), um den Weg für eine Neuvergabe der Kehrichtabfuhr zu öffnen (vgl. hierzu Stefan Scherler, Abbruch und Wiederholung von Vergabeverfahren, in: Jean-Baptiste Zufferey/Hubert Stöckli [Hrsg.], Aktuelles Vergaberecht 2008, Zürich 2008, S. 285 ff.).
5. Schliesslich hat das Kantonsgericht der Beschwerdegegnerin Schadenersatz im Umfang von 10'800 Franken zugesprochen, weil der Beschwerdeführer dieser den mündlich erteilten Auftrag, die Kehrichtabfuhr einstweilig bis zum Abschluss des neuen Vertrags weiter zu besorgen, zur Unzeit entzogen habe. Den Schaden sah sie in den Lohnzahlungen für Angestellte, deren Arbeitsverhältnisse die Beschwerdegegnerin nicht kurzfristig kündigen konnte.
5.1 Der Beschwerdeführer bringt diesbezüglich vor, angesichts des eingetretenen Vertrauensverlustes habe er durchaus sachliche Gründe gehabt, den Vertrag mit der Beschwerdegegnerin unverzüglich zu kündigen. Um einer möglichen Unterbrechung der Kehrichtabfuhr zuvorzukommen, sei er gezwungen gewesen, den Auftrag sofort auf einen Dritten zu übertragen. Er bestreitet mithin, dass eine Kündigung zur Unzeit im Sinne von Art. 404 Abs. 2 OR und eine entsprechende Schadenersatzpflicht gegeben ist.
5.2 Die Argumentation des Beschwerdeführers vermag nicht zu überzeugen: Während der letzten fünf Jahre hatte die Beschwerdegegnerin die Kehrichtabfuhr auf dem Gebiet der Verbandsgemeinden zu seiner vollen Zufriedenheit besorgt und kurz zuvor im Vergabeverfahren erneut den Zuschlag erhalten. Bei diesen Gegebenheiten hatte sie sich offensichtlich darauf eingerichtet, den Auftrag für weitere fünf Jahre zu erfüllen, und konnte die für die provisorische Weiterführung der Kehrichtabfuhr getroffenen Dispositionen nicht ohne weiteres innert einiger weniger Tage rückgängig machen. Dessen ungeachtet hat ihr der Beschwerdeführer den Entzug des Auftrags per Ende Juli erst am 26. dieses Monats mitgeteilt, wobei sich die kurzfristige Kündigung gar erst aus dem tags darauf verschickten Schreiben (mit der korrigierten Jahreszahl 2006 anstatt 2007) unmissverständlich ergab. Auch wenn sich die an den Zuschlag anschliessenden Vertragsverhandlungen schwierig gestalteten und sich der Beschwerdeführer unter Druck gesetzt fühlen mochte, ist nicht einzusehen, inwiefern das Vertrauensverhältnis zwischen den Vertragspartnern damals derart schwerwiegend gestört war, dass Anlass für eine nahezu fristlose Kündigung bestand. Zwar weigerte sich die Beschwerdegegnerin hartnäckig, einzusehen, dass ihren Forderungen bezüglich eines allfälligen Unterschreitens der Abfallmenge bereits aus rechtlichen Gründen nicht entsprochen werden konnte. Ihr diesbezügliches Verhalten vermochte aber für sich allein ihre Vertrauenswürdigkeit hinsichtlich der Besorgung der Kehrichtabfuhr kaum in Frage zu stellen. Weil der Beschwerdeführer zudem nicht dartut, dass er Anlass hatte, eine Schlechterfüllung des Auftrags zu befürchten, wenn er eine Kündigung mit einer den Umständen angemessenen Frist ausgesprochen hätte, ist kein sachlicher Grund für eine derart überstürzte Kündigung ersichtlich. Im Übrigen konnte eine mangelhafte Ausführung des Auftrags bereits deshalb nicht ernsthaft befürchtet werden, weil die Beschwerdegegnerin in diesem Zeitpunkt noch auf ein - notfalls auf dem Rechtsweg erzwungenes - Zustandekommen des Vertrags hoffte.
5.3 Da die Höhe des zugesprochenen Schadenersatzes vor Bundesgericht nicht beanstandet wurde, kann insoweit auf die (überzeugenden) Erwägungen des angefochtenen Entscheids verwiesen werden.
6. 6.1 Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen und der angefochtene Entscheid aufzuheben, soweit er den Vertragsschluss und die Kostenregelung betrifft; im Übrigen - d.h. bezüglich der Verpflichtung des Beschwerdeführers zur Bezahlung von Schadenersatz - wird die Beschwerde abgewiesen. Die Sache ist zur Neuverlegung der Kosten des kantonalen Verfahrens an das Kantonsgericht zurückzuweisen.
6.2 Bei diesem Verfahrensausgang unterliegt der Beschwerdeführer nur in einem Nebenpunkt, so dass ihm bloss ein Fünftel der Verfahrenskosten auferlegt wird; die restlichen Kosten hat die Beschwerdegegnerin zu tragen (Art. 65 f. BGG). Obschon der Beschwerdeführer vor Bundesgericht anwaltlich vertreten war, ist ihm keine Parteientschädigung auszurichten, zumal öffentlichen Körperschaften - auch im Falle eines Obsiegens - in aller Regel keine solche zugesprochen wird, wenn sie im Rahmen ihres amtlichen Wirkungskreises handeln (Art. 68 Abs. 2 und Abs. 3 BGG; vgl. BGE 134 II 117 E. 7 S. 118 f.). Der Beschwerdeführer hat seinerseits der Beschwerdegegnerin eine reduzierte Parteientschädigung auszurichten (Art. 68 Abs. 1 und Abs. 2 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und die Ziffern 2a, 4 sowie 5 des Dispositivs des Urteils des Kantonsgerichts von Graubünden vom 11. März 2008 werden aufgehoben; im Übrigen wird die Beschwerde abgewiesen.
2. Die Gerichtskosten von 5'000 Franken werden zu vier Fünfteln der Beschwerdegegnerin und zu einem Fünftel dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer wird verpflichtet, der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine reduzierte Parteientschädigung von 500 Franken auszurichten.
4. Die Sache wird zur Neuverlegung der Kosten des kantonalen Verfahrens an das Kantonsgericht von Graubünden zurückgewiesen.
5. Dieses Urteil wird den Parteien und dem Kantonsgericht von Graubünden, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 5. November 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Häberli