Sachverhalt:
A. Die Fibre Lac SA erstellte nach der Liberalisierung des Fernmeldewesens in der Schweiz ein Glasfaserkabelnetz (sog. Fibre Network), das die Grossstädte Genf, Lausanne, Bern, Basel und Zürich verbindet. Sie verlegte zu diesem Zweck entlang der Nationalstrassen ein Bündel von Rohren, in die sie die Glasfaserkabel einführte.
Das Tiefbauamt des Kantons Bern erteilte der Fibre Lac SA am 10. Mai 2000 die für die Verlegung erforderliche strassenpolizeiliche Bewilligung. Sie hielt unter anderem fest, dass mit dem Bau begonnen werden dürfe, sobald die Vereinbarung über die Benützung der Kabelrohranlage zwischen der Fibre Lac SA und dem Tiefbauamt des Kantons Bern unterschrieben sei. Am 16. Mai 2000 erfolgte die Unterzeichnung der erforderlichen Vereinbarung, am 13. Juni 2000 die Genehmigung durch das Bundesamt für Strassen.
Die Fibre Lac SA erklärte in der Folge, sie erachte die Vereinbarung vom 16. Mai 2000 für ungültig, weil sie gegen Art. 35 Abs. 4 und Art. 37 Abs. 1 des Fernmeldegesetzes vom 30. April 1997 (FMG; SR 784.10) verstosse und sie aufgrund des grossen Zeitdrucks faktisch zum Abschluss gezwungen gewesen sei. Der Kanton Bern stellte sich dieser Auffassung entgegen und warf der Fibre Lac SA seinerseits vor, sie komme ihren vertraglichen Verpflichtungen nicht nach.
Als die Versuche, eine Einigung zu erzielen, gescheitert waren, erhob die Fibre Lac SA am 20. Dezember 2002 gegen den Kanton Bern bei dessen Verwaltungsgericht Klage auf Bezahlung von 14'515'769 Franken, zuzüglich 5 % Verzugszins seit dem 7. August 2000. Weiter beantragte sie, es sei festzustellen, dass das Eigentum an der von ihr genutzten Infrastruktur - insbesondere an 12 Rohren mit je 40 Millimetern Durchmesser sowie an sämtlichen Spleiss- und Zugschächten - ihr zustehe. Schliesslich verlangte sie, es sei der Kanton Bern anzuweisen, ihr die Bewilligung zur Benützung der Nationalstrasse und des öffentlichen Grundes auf seinem Hoheitsgebiet gemäss den Plänen für die Infrastruktur für 12 Rohre mit je 40 Millimetern Durchmesser sowie für die dazugehörigen Spleiss- und Zugschächte zu erteilen.
Der Kanton Bern erhob Widerklage und stellte den Antrag, es sei auf die Klage nicht einzutreten, eventualiter sei sie abzuweisen und es sei die Klägerin zu verpflichten, die für den Bau der Infrastruktur ausserhalb des Eigentums der Nationalstrasse notwendigen Dienstbarkeiten und Durchleitungsrechte auf eigene Kosten zu erwerben und die erworbenen Rechte kostenlos auf den Beklagten und Widerkläger zu übertragen.
Das Verwaltungsgericht beschränkte das Verfahren auf die Frage seiner Zuständigkeit, das grundsätzliche Bestehen eines Anspruchs der Fibre Lac SA gegenüber dem Kanton Bern sowie auf die widerklageweise erhobenen Feststellungs-, Leistungs- und Gestaltungsbegehren. Am 11. April 2006 bejahte das Gericht seine Zuständigkeit. Es stellte ausserdem fest, dass die Ansprüche der Klägerin nicht verjährt seien und ihr insoweit keine Ansprüche gegen den Beklagten zustünden, als der gerichtlich zu bestimmende wirtschaftliche Wert der Wiederherstellung des ursprünglichen Zustands jenen der von der Klägerin erbrachten Leistungen übersteige und dass im umgekehrten Fall die Zusprechung einer Geldleistung vorbehalten bleibe. Schliesslich wies das Verwaltungsgericht die beiden weiteren Begehren der Klägerin ab und verpflichtete sie in Gutheissung der Widerklage, die für den Bau der Infrastruktur ausserhalb des Eigentums der Nationalstrasse notwendigen Dienstbarkeiten und Durchleitungsrechte auf eigene Kosten zu erwerben und die erlangten Rechte kostenlos auf den Beklagten zu übertragen.
B. Der Kanton Bern erhebt beim Bundesgericht Verwaltungsgerichtsbeschwerde und beantragt, das Urteil des Verwaltungsgerichts vom 11. April 2006 aufzuheben und auf die Klage nicht einzutreten, eventuell die Sache mit der entsprechenden Weisung an das Verwaltungsgericht zurückzuweisen. Zudem stellt der Kanton Bern mehrere Eventualanträge (Verfahren 2A.296/2006).
Die Fibre Lac SA gelangt ebenfalls mit Verwaltungsgerichtsbeschwerde an das Bundesgericht. Sie ersucht um Aufhebung des Urteils vom 11. April 2006, ausser bezüglich der Feststellung, dass ihre Ansprüche nicht verjährt seien. Zudem sei festzustellen, dass die am 16. Mai 2000 zwischen ihr und dem Kanton Bern abgeschlossene Vereinbarung nichtig oder eventualiter ungültig sei und dass das Eigentum an der von ihr genutzten Infrastruktur - insbesondere an den 12 Rohren mit je 40 Millimetern Durchmesser sowie an sämtlichen Spleiss- und Zugschächten gemäss Plänen - ihr zustehe bzw. ihr eventualiter hälftiges Miteigentum an der gesamten Infrastruktur zukomme (Verfahren 2A.301/2006).
Die Fibre Lac SA beantragt, es sei auf die vom Kanton Bern erhobene Verwaltungsgerichtsbeschwerde nicht einzutreten, eventuell sei sie vollumfänglich abzuweisen.
Der Kanton Bern stellt den Antrag, die Beschwerde der Fibre Lac SA abzuweisen.
Das Verwaltungsgericht ersucht um Abweisung beider Beschwerden.
Schliesslich beantragt das Bundesamt für Strassen, die Beschwerde des Kantons Bern gutzuheissen und jene der Fibre Lac SA abzuweisen.
C. Das Bundesamt für Kommunikation hat am 5. Januar 2007 einen Amtsbericht zu den fernmelderechtlichen Fragen erstattet, welche die Beschwerden aufwerfen. Die Parteien und das Verwaltungsgericht haben Gelegenheit erhalten, zum eingeholten Amtsbericht Stellung zu nehmen.
D. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde der Fibre Lac SA am 14. Juni 2006 die aufschiebende Wirkung zuerkannt.
Erwägungen:
1. 1.1 Der angefochtene Entscheid erging noch vor dem Inkrafttreten des Bundesgerichtsgesetzes (BGG) am 1. Januar 2007. Gemäss Art. 132 Abs. 1 BGG richtet sich das Verfahren daher nach den Bestimmungen des Bundesrechtspflegegesetzes (OG).
1.2 Die beiden erhobenen Beschwerden richten sich gegen das gleiche Urteil und werfen teilweise die gleichen Rechtsfragen auf. Es rechtfertigt sich daher, sie gemeinsam zu behandeln.
1.3 Die Fibre Lac SA machte ihre Ansprüche beim Verwaltungsgericht mit Klage geltend, da sich diese aus dem mit dem Kanton Bern geschlossenen öffentlich-rechtlichen Vertrag ergeben. Dieser beschlägt weitgehend eine durch Bundesverwaltungsrecht (Art. 35 und 37 FMG) geregelte Materie. Ob und wieweit der Vertrag wegen Verstosses gegen zwingende Normen des Fernmeldegesetzes anfechtbar ist bzw. einer Korrektur bedarf, beurteilt sich insoweit ebenfalls nach Bundesverwaltungsrecht, weshalb der diesbezügliche kantonale Gerichtsentscheid der Verwaltungsgerichtsbeschwerde unterliegt (vgl. BGE 126 III 431; 124 II 436, nicht publizierte E. 1). Kraft Sachzusammenhangs gilt dies auch für die allenfalls nicht durch Bundesverwaltungsrecht geregelten weiteren Gesichtspunkte (vgl. BGE 128 I 46 E. 1b).
2. 2.1 Der Kanton Bern macht geltend, die Vorinstanz hätte auf die bei ihr erhobene Klage der Fibre Lac SA nicht eintreten dürfen. Die in der Vereinbarung vom 16. Mai 2000 enthaltenen Regelungen stellten lediglich Nebenbestimmungen zur Bewilligung des Tiefbauamts des Kantons Bern vom 10. Mai 2000 dar, so dass dagegen nur die Beschwerde zulässig sei; eine solche sei von der Fibre Lac SA nicht ergriffen worden.
2.2 Der zunächst erhobene Vorwurf, die Vorinstanz habe bei der Prüfung der Eintretensfrage den Sachverhalt teilweise offensichtlich unvollständig und unrichtig festgestellt, entbehrt der Grundlage. Was der Kanton Bern in diesem Zusammenhang vorbringt, bezieht sich allein auf die rechtliche Qualifizierung der Vereinbarung vom 16. Mai 2000. Ebenso wenig wird in der Beschwerde begründet, inwiefern die vorinstanzliche Beurteilung der genannten Vereinbarung als eigenständiger Rechtsakt die angerufenen Normen des Bundesrechts (Art. 35 FMG; Art. 44 des Bundesgesetzes vom 8. März 1960 über die Nationalstrassen [NSG; SR 725.11] und Art. 29 der Verordnung vom 18. Dezember 1995 über die Nationalstrassen [NSV; SR 725.111]) verletzen sollte. Zu prüfen ist deshalb einzig, ob die Vorinstanz ihre Zuständigkeit in willkürlicher Anwendung des kantonalen Rechts bejaht.
2.3 Der Kanton Bern weist zwar zu Recht auf verschiedene inhaltliche Bezüge zwischen der Bewilligung vom 10. Mai 2000 und der kurz darauf geschlossenen Vereinbarung hin. Das ändert aber nichts daran, dass die vielfältigen Fragen, welche der Bau der Telekommunikations-Infrastruktur aufgeworfen hat, mit zwei unterschiedlichen verwaltungsrechtlichen Instrumenten (Verfügung und Vertrag) geregelt wurden. Insbesondere hat das Tiefbauamt die Vereinbarung nicht als Teil seiner Verfügung vom 10. Mai 2000 erklärt. Die Vorinstanz zeigt auch auf, dass die Bewilligung und die Vereinbarung - trotz gegenseitiger Bezüge - verschiedene Inhalte aufweisen. Auch wenn es möglich gewesen wäre, die anstehenden Fragen in grösserem Umfang oder sogar ausschliesslich in Verfügungsform zu regeln, hat die Vorinstanz berücksichtigt, dass der Kanton Bern bewusst zwei unterschiedliche Handlungsformen verwendet hat und dass das Bundesrecht eine vertragliche Regelung einzelner Fragen grundsätzlich zulässt. Diese Beurteilung ist sachlich zumindest vertretbar. Die Vorinstanz hat ihre Zuständigkeit deshalb nicht in willkürlicher Anwendung des kantonalen Verfahrensrechts bejaht.
3. 3.1 Für den Fall der Bejahung der verwaltungsgerichtlichen Zuständigkeit verlangt der Kanton Bern die Abweisung der Klage der Fibre Lac SA. Er ist der Ansicht, die Vorinstanz gelange gestützt auf eine offensichtlich unvollständige Sachverhaltsfeststellung und in falscher Auslegung der Verjährungsbestimmungen zum Schluss, die Fibre Lac SA habe sich rechtzeitig auf die Unverbindlichkeit der Vereinbarung vom 16. Mai 2000 berufen.
3.2 Was der Kanton Bern zur Begründung dieser Rüge vorbringt, überzeugt nicht. Die Vorinstanz übersieht die angeblich ausser Acht gelassenen Umstände nicht, sondern gewichtet sie lediglich anders. Die Kritik, die Fibre Lac SA hätte sich bereits vor der Ablieferung von zwei Gutachten über die Rechtslage Klarheit verschaffen müssen, übersieht die zahlreichen Unsicherheiten bei der praktischen Umsetzung der neuen fernmelderechtlichen Bestimmungen. Dass manche Unklarheiten bestanden, zeigen nicht zuletzt die im angefochtenen Entscheid erwähnten Kontakte der Fibre Lac SA mit den Behörden und der verschiedenen Behörden untereinander. Die erhobene Kritik übersieht, dass die Verwirklichung des Projekts keineswegs allein eine Anwendung von Art. 35 Abs. 4 FMG erforderte, sondern viele weitere Fragen aufwarf.
3.3 Ebenfalls unbegründet ist das vom Kanton Bern gestellte Subeventualbegehren. Die Vereinbarung vom 16. Mai 2000 regelt die finanziellen Belange, welche der Bau der Telekommunikations-Infrastruktur aufwirft. Bei der Prüfung, ob die getroffene Regelung dem Gesetz nicht widerspricht, ist auch Art. 35 Abs. 4 FMG mitzuberücksichtigen.
4. 4.1 Die Fibre Lac SA macht geltend, die von ihr mit dem Kanton Bern geschlossene Vereinbarung verstosse gegen Art. 37 Abs. 1 FMG.
4.2 Die Vorinstanz gelangt zum Schluss, dass die von den Parteien getroffene Regelung des Eigentums an der Kabelrohranlage zwar allenfalls Art. 37 Abs. 1 FMG widerspreche, sich die Fibre Lac SA jedoch nach Treu und Glauben nicht mehr auf die Unzulässigkeit der von ihr selber vorgeschlagenen Abmachung berufen könne. Die Fibre Lac SA macht demgegenüber geltend, Art. 37 Abs. 1 FMG sei zwingender Natur, weshalb davon nicht abgewichen werden dürfe.
4.3 Die erwähnte Norm fand erst im Laufe der parlamentarischen Beratungen Eingang in das neue Fernmeldegesetz. Es sollte sichergestellt werden, dass die unterirdischen Leitungen, die mit der Reform der früheren Telecom-PTT aus dem Verwaltungsvermögen des Bundes ausschieden, weiterhin dieser Unternehmung gehören und nicht aufgrund des Akzessionsprinzips (Art. 667 Abs. 1 ZGB) dem Grundeigentümer zufallen. Zugleich sollten auch neue Anbieter im Fernmeldebereich der Telecom-PTT bzw. der späteren Swisscom gleichgestellt werden (Votum von Ständerat Kurt Schüle, AB 1997 S. 100). Die Regelung von Art. 37 Abs. 1 FMG bezweckt demnach, die alte Ordnung, wonach die Fernmeldeleitungen im Eigentum des Telekommunikationsunternehmens stehen, weiterzuführen und sie auf neue Konzessionäre auszudehnen (vgl. auch Peter R. Fischer/Oliver Sidler, Fernmelderecht, in: Schweizerisches Bundesverwaltungsrecht, Band V: Informations- und Kommunikationsrecht, hrsg. von Rolf H. Weber, 2. Aufl. Basel/Genf/München 2003, S. 231).
Aus dieser Entstehungsgeschichte ergibt sich, dass Art. 37 Abs. 1 FMG lediglich das Eigentum an Leitungen regelt, die schon bisher von Fernmeldedienstanbietern genutzt wurden oder die sie für ihre eigenen Zwecke neu erstellen. Hingegen schliesst die Norm nicht aus, dass Dritte solche Leitungen bauen und daran Eigentum erwerben. So sieht der Gesetzestext ausdrücklich vor, dass nicht nur Leitungen im Eigentum der Konzessionärinnen stehen, die sie selbst erstellen, sondern auch solche, die sie von Dritten erwerben. Insbesondere ist es auch dem Eigentümer von Boden im Gemeingebrauch unbenommen, selber Kabelkanäle zu erstellen und diese den Anbietern von Fernmeldedienstleistungen zur Nutzung zu überlassen (ebenso das von der Beschwerdeführerin in Auftrag gegebene Rechtsgutachten von Tobias Jaag/Markus Rüssli vom 4. April 2001, S. 17). Die revidierte Verordnung über die Fernmeldedienste sieht nun auch ausdrücklich vor, dass die Konzessionärinnen verpflichtet werden können, freie Infrastrukturen von Strassenanlagen gegen eine angemessene Entschädigung ihres Eigentümers zu benützen (Art. 78 Abs. 2 FDV in der Fassung vom 9. März 2007 bzw. Art. 38a Abs. 2 FDV in der Fassung vom 7. März 2003). Der Strasseneigentümer kann ein Interesse daran haben, selber Kabelkanäle zu bauen, um mehrfache Bauarbeiten zu vermeiden und eine optimale Verlegung der Leitungen sicherzustellen.
4.4 Das zuletzt genannte Motiv prägte offensichtlich die Verhandlungen zwischen den Parteien. Der Kanton Bern war bestrebt, bei der Erstellung der neuen Kabelkanäle Kapazitätsreserven zu schaffen, um auch künftigen Bedürfnissen Rechnung tragen zu können. In der getroffenen Vereinbarung wurde deshalb vorgesehen, nicht nur die von der Beschwerdeführerin benötigten zwölf Rohre zu bauen, sondern weitere zwölf Einheiten, über deren Nutzung der Kanton Bern verfügt. Die Erstellung der Kabelrohranlage oblag der Fibre Lac SA, dem Kanton Bern dagegen wurde das Eigentum an der neuen Anlage eingeräumt.
Nach dem Wortlaut der Vereinbarung geht das Eigentum an der Kabelrohranlage erst nach dem Bau auf den Kanton Bern über. Diese Regelung unterstellt, dass vorher die Fibre Lac SA Eigentümerin ist. Für eine solche Ordnung ist jedoch ein vernünftiger Grund nicht ersichtlich, und es ist zweifelhaft, ob sie dem wirklichen Willen der Parteien entspricht. Die zwölf Rohre, welche die Fibre Lac SA nicht selber nutzen will, werden von Art. 37 Abs. 1 FMG nicht erfasst, und es ist nicht ersichtlich, wieso sie nicht von Anfang an im Eigentum des Werkeigentümers stehen sollten (vgl. angefochtenes Urteil E. 7.2.6). Aber auch die zwölf Rohre, an denen der Fibre Lac SA ein Nutzungsrecht eingeräumt wird, stehen gestützt auf Art. 37 Abs. 1 FMG weder während der Bauzeit noch nachher zwingend im Eigentum der Fibre Lac SA. Was die Parteien mit der erwähnten Regelung bezweckten, kann dahingestellt bleiben. Auf jeden Fall schliesst die erwähnte Bestimmung nicht aus, dass ein Fernmeldedienstanbieter für einen Strasseneigentümer einen Kabelrohrblock baut und dieser - von Anfang an oder erst nach Abschluss der Bauarbeiten - in dessen Eigentum steht. Wenn es Art. 37 Abs. 1 FMG zulässt, dass der Strasseneigentümer selber Fernmeldeinfrastrukturanlagen baut und das Eigentum an ihnen erwirbt, ist es auch zulässig, dass er sich solche von einer Drittperson erstellen lässt.
4.5 Die Eigentumsregelung in der Vereinbarung der Parteien widerspricht daher Art. 37 Abs. 1 FMG nicht. Das Begehren der Fibre Lac SA auf Feststellung ihres (Mit-)Eigentums an der von ihr erstellten Infrastrukturanlage ist daher unbegründet.
5. 5.1 Die Vorinstanz nimmt zur Zulässigkeit der vereinbarten Leistungspflichten nicht abschliessend Stellung. Sie behält sich vor, darüber zu befinden, wenn deren Wert in quantitativer Hinsicht bestimmt ist. Insbesondere lässt der angefochtene Entscheid offen, ob eine Verletzung von Art. 35 Abs. 4 FMG vorliegt.
5.2 Die Parteien erklären in Ziff. 8.1 ihrer Vereinbarung ausdrücklich, dass in Übereinstimmung mit Art. 35 Abs. 4 FMG keine Gebühren für die Nutzung des Bodens geschuldet werden. Zugleich bringen sie aber einen Vorbehalt zugunsten einer näher umschriebenen kantonalen Gebühr an. Da die genannte Gesetzesbestimmung kostendeckende Gebühren nicht ausschliesst, ist davon auszugehen, dass die Parteien keine von ihr abweichende Regelung treffen wollten. Es fragt sich indessen, ob die vereinbarten Leistungen gegen andere Vorschriften verstossen. Die Fibre Lac SA rügt ebenfalls eine Verletzung des Äquivalenzprinzips. Der Kanton Bern dagegen behauptet, der Fibre Lac SA die Mehrkosten, die durch das Verlegen der zusätzlichen Rohre entstanden sind, direkt bezahlt zu haben. Auf die damit aufgeworfenen Fragen ist nur so weit einzugehen, als die Vorinstanz dazu Stellung nimmt. Das betrifft insbesondere verschiedene Fragen der Vertragsauslegung.
6. 6.1 Nach dem angefochtenen Entscheid hat die Fibre Lac SA Anspruch auf eine Entschädigung für die Mehrkosten, welche die Verlegung der zwölf vom Kanton Bern zusätzlich bestellten Rohre mit sich bringt. Die Fibre Lac SA verlangt demgegenüber, dass der Kanton Bern die Hälfte der Erstellungskosten für die Anlage mit 24 Rohren übernehme.
6.2 Es steht fest, dass die Fibre Lac SA ursprünglich lediglich eine Kabelrohranlage mit zwölf Rohren für sich selbst bauen wollte. In diesem Fall hätte sie für deren Kosten allein aufkommen müssen. Später einigten sich die Parteien, zusätzlich zwölf Rohre für den Kanton Bern zu erstellen. Wie die Vorinstanz zutreffend erklärt, handelt es sich dabei um eine Zusatzbestellung, die nicht auf einen Gesellschaftswillen (animus societatis) der Vertragsparteien schliessen lässt. Die Fibre Lac SA kann deshalb vom Kanton Bern nicht verlangen, gestützt auf Art. 531 Abs. 2 OR die Hälfte der Baukosten der gesamten Anlage zu tragen. Sie hat gestützt auf Art. 35 Abs. 4 FMG lediglich Anspruch darauf, für die Nutzung von Grund und Boden, soweit sie den Gemeingebrauch nicht beeinträchtigt, keine Entschädigung bezahlen zu müssen. Indessen hat sie kein Recht darauf, dass sich der Strasseneigentümer am Projekt ebenfalls beteiligt, um auf diese Weise eine Senkung der Kosten der eigenen Leitungen zu erreichen. Aufgrund der Umstände, die zur Vereinbarung zwischen den Parteien führten, kann nicht angenommen werden, dass der Kanton Bern der Fibre Lac SA in weiterem Umfang entgegenkommen wollte, als er von Gesetzes wegen verpflichtet war.
Die vorinstanzliche Feststellung, dass der Kanton Bern der Fibre Lac SA lediglich die durch die Zusatzbestellung verursachten Mehrkosten zu entschädigen hat, ist demnach nicht zu beanstanden.
7. 7.1 Die Vereinbarung trifft in Ziff. 2.3 Abs. 2 und Ziff. 7.1 Abs. 2 eine Entschädigungsregelung für die erwähnte Zusatzbestellung. Nach Auffassung der Vorinstanz leistet jedoch der Kanton Bern dadurch eine zusätzliche Entschädigung, dass er in der Vereinbarung auf seinen Wiederherstellungsanspruch gemäss Art. 35 Abs. 2 FMG verzichtet. Die Fibre Lac SA bestreitet einen solchen Auskauf der Wiederherstellungspflicht. Sie verweist auf Ziff. 15 der Vereinbarung, woraus sich genau das Gegenteil ergebe.
7.2 Nach der erwähnten Vertragsbestimmung kann der Werkeigentümer bei Auslaufen des Nutzungsrechts verlangen, dass der letzte Benützer die Nationalstrassen-Infrastruktur wieder für seine Bedürfnisse (sc. jene des Werkeigentümers) herrichtet. Der Kanton Bern macht geltend, unter Nationalstrassen-Infrastruktur sei nicht die Kabelrohranlage zu verstehen, sondern die übrige Infrastruktur, die im Zusammenhang mit der Kabelrohranlage benutzt werde, z.B. Zugangswege oder Wasserableitungen.
Für diese Auslegung spricht neben der systematischen Stellung vor allem der Wortlaut. Für die Kabelrohranlage wird gemäss Ziff. 1.1 stets der Ausdruck "Infrastruktur" verwendet. Dass unter Nationalstrassen-Infrastruktur etwas anderes zu verstehen ist, ergibt sich beispielsweise aus Ziff. 3.2 der Vereinbarung, wo die beiden genannten Begriffe nebeneinander verwendet werden.
Ziffer 15 verpflichtet somit die Fibre Lac SA nur in einem sehr bescheidenen Umfang zur einer Wiederherstellung. Die vorinstanzliche Feststellung ist deshalb nicht zu beanstanden, dass die Vereinbarung die Fibre Lac SA mit Bezug auf die Kabelrohranlage von der Pflicht zur Wiederherstellung des ursprünglichen Zustands entbinde.
8. 8.1 Nach Ansicht der Vorinstanz sieht Ziff. 8.1 der Vereinbarung eine Abgeltung für den Wegfall der Wiederherstellungspflicht vor. Die Fibre Lac SA kritisiert diese Auslegung als willkürlich. Auch der Kanton Bern hält die vorinstanzliche Auffassung für zweifelhaft. Er stellt zwar nicht in Frage, dass der Vertrag die Fibre Lac SA von der Wiederherstellungspflicht befreit, doch sollten damit nicht die Mehrkosten für die zwölf für den Kanton Bern erstellten Rohre entschädigt werden. Vielmehr handle es sich dabei um eine Zusatzleistung, da der Kanton Bern der Fibre Lac SA die Mehrkosten bereits direkt bezahlt habe.
8.2 Ziffer 8.1 der Vereinbarung trifft einen Vorbehalt für eine kantonale "Gebühr im Zusammenhang mit einer Wertreduktion der bestehenden Anlagen, von Erschwernissen für den Unterhalt des Eigentümers, von Haftungsrisiken bei Bauarbeiten auf eigenen Anlagen". Weiter wird erklärt, dass diese kantonale Gebühr durch Leistungen des Benutzers für den Eigentümer beglichen werden kann.
Der Wortlaut legt es nicht nahe, in dieser Bestimmung einen Auskauf der Wiederherstellungspflicht gemäss Art. 35 Abs. 2 FMG zu sehen. Nach dem Text wird lediglich ein allgemeiner Vorbehalt angebracht, aber keine konkrete Gebühr ausdrücklich genannt. Ausserdem erwähnt Ziff. 8.1 lediglich die Möglichkeit, eine allfällige Gebühr durch Naturalleistungen des Benutzers zu begleichen. Der Bestimmung lässt sich aber nicht entnehmen, dass eine bestimmte Gebühr bereits bei Vertragsschluss durch die Erstellung von zwölf zusätzlichen Rohren entgolten sein soll.
Wenn der Wiederherstellungspflicht eine so wichtige Rolle zukommt, wie der angefochtene Entscheid unterstellt, hätte darüber eine klare vertragliche Regelung erwartet werden dürfen. Die Vorinstanz unterlässt es, den Willen der Parteien in diesem Punkt festzustellen. Aus den Rechtsschriften geht indessen hervor, dass über die Wiederherstellungspflicht in den Verhandlungen nicht oder höchstens ganz am Rande gesprochen wurde. Es ist weiter unbestritten, dass die Parteien nicht an einen Auskauf der Wiederherstellungspflicht dachten. Demzufolge gibt es auch keine Anhaltspunkte dafür, dass die vorinstanzliche Auslegung dem wirklichen Willen der Parteien entsprechen könnte.
Ausserdem ergeben sich aus den Umständen, unter denen die Vereinbarung vom 16. Mai 2000 abgeschlossen wurde, keine Hinweise, dass unter der "Wertreduktion der bestehenden Anlagen" in Ziff. 8.1 der Wegfall der Wiederherstellungspflicht gemäss Art. 35 Abs. 2 FMG gemeint sein könnte. Eine solche Interpretation verkennt denn auch die Lage der Parteien in wesentlichen Punkten. Entgegen der vorinstanzlichen Ausführungen ist es keineswegs sicher, dass die Kabelrohranlage nach Ablauf der vereinbarten 25-jährigen Nutzungsdauer zu einer Wertreduktion der Nationalstrasse führt. Wie es sich damit verhält, ist vielmehr offen und im heutigen Zeitpunkt nicht zuverlässig zu beurteilen. Es ist denkbar, dass im Jahr 2025 weiterhin ein Interesse an der Nutzung der Kabelrohre besteht und der Kanton Bern diese wiederum - möglicherweise sogar für eine lange Dauer - weitervermieten kann. Diesfalls bewirkte die Anlage für den Strasseneigentümer - selbst bei Annahme eines gewissen Unterhaltsbedarfs - nicht eine Minderung, sondern eine Erhöhung des Werts seines Eigentums. Zudem ist unklar, ob der Strasseneigentümer selbst bei einem Verzicht auf eine weitere Nutzung der Kabelrohranlage überhaupt ein Interesse an deren Entfernung hat. Ist es somit ungewiss, ob der Wegfall der Wiederherstellungspflicht im Jahr 2025 einen Minderwert des Strasseneigentums bewirkt, so kann darin nicht eine Wertreduktion gemäss Ziff. 8.1 der Vereinbarung gesehen werden. Die vorinstanzliche Auslegung verstösst gegen das Vertrauensprinzip, das auch bei öffentlich-rechtlichen Verträgen Anwendung findet, soweit nicht ein anderer Wille der Parteien nachgewiesen ist (BGE 122 I 328 E. 4e S. 335).
Schliesslich ist auch nicht ersichtlich, dass vom Kanton Bern zu wahrende öffentliche Interessen die Auslegung der Vorinstanz geböten und ihnen deshalb nach dem Vertrauensprinzip ein massgebliches Gewicht zukäme. Der Wegfall der Wiederherstellungspflicht ist die logische Folge der von den Parteien getroffenen Eigentumsregelung. Der Kanton Bern erhielt damit das Eigentum an der neu erstellten Kabelrohranlage mit der Chance, diese auch nach Ablauf der 25-jährigen Nutzungsdauer gewinnbringend vermieten zu können. Umgekehrt entfiel damit die Pflicht der Fibre Lac SA, bei Aufgabe der Nutzung von zwölf Rohren den ursprünglichen Zustand wieder herzustellen, zu der sie als Eigentümerin verpflichtet gewesen wäre. Als solche hätte die Fibre Lac SA ihre Rohre auch länger als 25 Jahre benutzen können und hätte höhere Gewinnchancen gehabt. Dem Verzicht auf die Wiederherstellungspflicht steht somit die Erlangung des Eigentums an der ganzen Anlage gegenüber. Der Kanton Bern führt selber aus, dass er die Vereinbarung in diesem Sinn verstanden habe und der Wegfall der Wiederherstellungspflicht die Gegenleistung für die Einräumung des Eigentums darstelle.
Die vorinstanzliche Auslegung, wonach in Ziff. 8.1 der Vereinbarung ein Entgelt für den Wegfall der Wiederherstellungspflicht der Fibre Lac SA abgemacht worden sei, ist mit dem Vertrauensprinzip nicht zu vereinbaren und verletzt deshalb Bundesrecht.
9. 9.1 Der angefochtene Entscheid bestimmt - wie erwähnt - die vertraglichen Leistungen der Parteien dem Grundsatz nach, die unter dem Gesichtswinkel von Art. 35 Abs. 4 FMG massgeblich sind. Der Kanton Bern rügt in seiner Beschwerde subsubeventualiter, dass die Vorinstanz verschiedene von ihm erbrachte Leistungen ohne Begründung ausser Acht lasse.
9.2 An erster Stelle macht er geltend, dass er den Bau der Kabelrohranlage im Standstreifen erlaubt habe, wodurch sich für die Fibre Lac SA die Baukosten und das Baurisiko vermindert hätten. Da der Standstreifen im Gemeingebrauch steht, darf ihn der Fernmeldedienstanbieter gemäss Art. 35 Abs. 4 FMG grundsätzlich entschädigungslos für den Bau von Leitungen und Kabelkanälen benutzen. Wohl hat er bei der Verlegung von Leitungen auf den Zweck und die Nutzung des in Anspruch genommenen Grundstücks Rücksicht zu nehmen (Art. 35 Abs. 2 FMG), doch schliesst dies eine Benutzung des Standstreifens nicht von vornherein aus. Die Erlaubnis, die Infrastruktur dort zu verlegen, stellt deshalb keine Leistung dar, für welche der Kanton Bern eine Entschädigung verlangen kann. Allerdings darf der Kanton für den allenfalls erhöhten Verwaltungsaufwand, der ihm durch die Verlegung im Standstreifen erwächst, kostendeckende Gebühren erheben (Art. 35 Abs. 4 FMG). Zulässig ist jedoch allein die Erhebung von Verwaltungs- und nicht auch von Benutzungsgebühren (Votum von Bundesrat Moritz Leuenberger, AB 1997 S 93; Markus Rüssli, Nutzung öffentlicher Sachen für die Verlegung von Leitungen, ZBl 102/2001 364).
9.3 Im vorinstanzlichen Verfahren hat der Kanton Bern eine Entschädigung wegen Wertverminderung des Standstreifens geltend gemacht. Er kann sich dafür auf Ziff. 8.1 der Vereinbarung stützen, die eine solche Gebührenerhebung ausdrücklich vorbehält. Er hat diesen Anspruch zwar nicht näher substanziert; doch war er dazu angesichts der Beschränkung des Streitgegenstands durch den Instruktionsrichter auch nicht gehalten. Die Vorinstanz wird deshalb zu prüfen haben, ob und in welchem Umfang der Kanton Bern für die behaupteten Leistungen Verwaltungsgebühren erheben darf. Dasselbe gilt mit Bezug auf die geltend gemachten erhöhten Ingenieurleistungen.
9.4 Schliesslich rügt der Kanton Bern, dass die Vorinstanz auch die Kosten berücksichtigt, die der Fibre Lac SA auf dem Nationalstrassenabschnitt zwischen km 179.000 und km 184.488 entstanden sind, obwohl dafür in der Verfügung vom 16. Mai 2000 eine besondere Regelung getroffen wurde. Der Vorwurf entbehrt der Grundlage, da die Vereinbarung vom 16. Mai 2000 auch diesen Abschnitt einschliesst und die Verfügung ausdrücklich auf die Vereinbarung verweist.
9.4 Schliesslich rügt der Kanton Bern, dass die Vorinstanz auch die Kosten berücksichtigt, die der Fibre Lac SA auf dem Nationalstrassenabschnitt zwischen km 179.000 und km 184.488 entstanden sind, obwohl dafür in der Verfügung vom 16. Mai 2000 eine besondere Regelung getroffen wurde. Der Vorwurf entbehrt der Grundlage, da die Vereinbarung vom 16. Mai 2000 auch diesen Abschnitt einschliesst und die Verfügung ausdrücklich auf die Vereinbarung verweist.
10. Die Fibre Lac SA beanstandet ebenfalls die Gutheissung der Widerklage des Kantons Bern. Ihr Einwand, dem Letzteren stehe gar kein Eigentum an den von ihr genutzten zwölf Rohren zu, ist - wie zuvor schon dargelegt wurde - unzutreffend. Was die Fibre Lac SA darüber hinaus vorbringt, vermag die vorinstanzliche Beurteilung nicht zu erschüttern. Es kann auf die Erwägungen im angefochtenen Entscheid (E. 8) verwiesen werden. Soweit sich die Fibre Lac SA gegen die Übernahme der Kosten wehrt, übersieht sie, dass die Vorinstanz die fraglichen Leistungen bei der Beurteilung der Zulässigkeit der Entschädigungsregelung anrechnet.
10. Die Fibre Lac SA beanstandet ebenfalls die Gutheissung der Widerklage des Kantons Bern. Ihr Einwand, dem Letzteren stehe gar kein Eigentum an den von ihr genutzten zwölf Rohren zu, ist - wie zuvor schon dargelegt wurde - unzutreffend. Was die Fibre Lac SA darüber hinaus vorbringt, vermag die vorinstanzliche Beurteilung nicht zu erschüttern. Es kann auf die Erwägungen im angefochtenen Entscheid (E. 8) verwiesen werden. Soweit sich die Fibre Lac SA gegen die Übernahme der Kosten wehrt, übersieht sie, dass die Vorinstanz die fraglichen Leistungen bei der Beurteilung der Zulässigkeit der Entschädigungsregelung anrechnet.
11. 11.1 Die Beschwerde des Kantons Bern erweist sich, abgesehen von einem untergeordneten Nebenpunkt, als unbegründet. Jene der Fibre Lac SA ist in dem Umfang begründet, als sie sich gegen die Feststellungen gemäss Ziffer 1 Spiegelstriche 2 und 3 des Dispositivs des angefochtenen Entscheids richtet. Letzterer ist in diesem Umfang aufzuheben. Zugleich ist die Sache zur Fortführung des Verfahrens im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Dem Kanton Bern sind die Kosten des von ihm eingeleiteten Beschwerdeverfahrens (2A.296/2006) aufzuerlegen, da er praktisch vollumfänglich unterliegt und die Streitsache seine Vermögensinteressen berührt (Art. 156 Abs. 1 und 2 OG). Zugleich hat er die Fibre Lac SA für dieses Verfahren angemessen zu entschädigen (Art. 159 Abs. 2 OG).
11.2 Die Kosten für das zweite Verfahren (2A.301/2006) sind den Parteien - entsprechend ihrem teilweisen Obsiegen bzw. Unterliegen - je zur Hälfte aufzuerlegen (Art. 156 Abs. 1 und 2 OG). Ausserdem hat der Kanton Bern der Fibre Lac SA eine reduzierte Parteientschädigung zu bezahlen. Der Kanton Bern hat demgegenüber keinen Anspruch auf eine Entschädigung (Art. 159 Abs. 2 OG).
Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerden werden teilweise gutgeheissen, und Ziffer 1 Spiegelstriche 2 und 3 des Urteils des Verwaltungsgerichts des Kantons Bern vom 11. April 2006 wird aufgehoben. Im Übrigen werden die Beschwerden abgewiesen.
Die Sache wird zur Fortführung des Verfahrens im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten im Verfahren 2A.296/2006 von Fr. 5'000.-- werden dem Kanton Bern auferlegt.
Die Gerichtskosten im Verfahren 2A.301/2006 von Fr. 10'000.-- werden den Parteien je zur Hälfte auferlegt.
3. Der Kanton Bern hat die Fibre Lac SA für beide Verfahren vor Bundesgericht mit insgesamt Fr. 10'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, dem Bundesamt für Strassen und dem Bundesamt für Kommunikation schriftlich mitgeteilt.
Lausanne, 19. März 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Küng