Aus den Erwägungen:
Eine Beschaffungsstelle kann deshalb ein Vergabeverfahren nicht aus beliebigen Gründen abbrechen, wiederholen oder neu durchführen. In § 18 öBG werden die möglichen Gründe aufgezählt (Botschaft des Regierungsrates vom 13.3.1998, in: Verhandlungen des Grossen Rates 1998, S. 308). Die Auftraggeberin darf das Verfahren abbrechen, wenn sie auf die Beschaffung verzichtet (Abs. 1). Sie kann das Verfahren abbrechen und wiederholen, wenn keine entsprechenden Angebote eingegangen sind, wenn aufgrund veränderter Rahmen- oder Randbedingungen oder wegfallender Wettbewerbsverzerrungen günstigere Angebote zu erwarten sind sowie wenn andere wichtige Gründe vorliegen (Abs. 2). Die Auftraggeberin kann überdies das laufende Verfahren abbrechen und ein neues Verfahren durchführen, wenn sie die verlangte Leistung wesentlich ändert (Abs. 3; vgl. zum Ganzen auch ZWR 2000 S. 52 ff.).
Das öBG unterscheidet damit zwischen Wiederholung und Neudurchführung des Verfahrens (vgl. auch Galli/Lehmann/Rechsteiner, a.a.O., Rz. 454, Fn. 2). Der Begriff der Wiederholung beinhaltet, dass das Verfahren nochmals unter den gleichen Bedingungen und dem gleichen Leistungsumfang durchgeführt wird. Die Neudurchführung setzt von Gesetzes wegen schon voraus, dass die verlangte Leistung sich wesentlich von der Leistung im vorgängigen Verfahren unterscheiden muss.
Die Beschwerdeführerin macht in ihrer Eingabe vom 17. Februar 2000 geltend, anstatt ein neues Verfahren anzusetzen, hätte die Vergabebehörde mit dem günstigsten Anbieter zusammen abklären müssen, ob dieser trotz Mindermass bereit sei, die Arbeiten zu den gleichen «Konditionen» auszuführen. Verhandlungen zwischen allen oder einzelnen Anbieterinnen und der Auftraggeberin über Preise, Preisnachlässe oder damit zusammenhängende Änderungen des Leistungsinhaltes sowie Abgebotsrunden sind grundsätzlich untersagt (§ 15 Abs. 2 öBG). Ausnahmsweise sind jedoch bei noch offenem Leistungsumfang Verhandlungen gestattet (Abs. 3). Da es sich vorliegend erwiesenermassen nicht um einen offenen Leistungsumfang handelte, war es dem Beschwerdegegner verboten, jedwede Verhandlungen zu führen, womit dessen Vorgehensweise in diesem Punkt nicht zu beanstanden ist.
Aus dem bisher Gesagten ergibt sich, dass nur ausnahmsweise, so z.B. bei offenem Leistungsumfang verhandelt werden darf. Eine unwesentliche Änderung der im Voraus bestimmten Leistung ist unbeachtlich. Handelt es sich um eine wesentliche Leistungsänderung, kann ein neues Vergabeverfahren durchgeführt werden. Zwischen Abgebotsrunde und Neudurchführung des Verfahrens besteht ein Spannungsverhältnis in der Art, dass, wenn das Verfahren aufgrund einer unwesentlichen Änderung neu aufgelegt würde, dies faktisch einer Abgebotsrunde gleichkäme. Keine Abgebotsrunde ist eine Neudurchführung aufgrund einer wesentlichen Leistungsänderung, bei welcher alle Anbieterinnen im Sinne der Gleichbehandlung die Möglichkeit erhalten, ihre Angebote im Grundsatz neu zu berechnen. Dies ist der Fall, wenn neue Leistungsteile verlangt werden oder sich mengenmässige Änderungen in einem bestimmten Umfang ergeben.
b) Die Vergabebehörde besitzt im Bereich von § 18 Abs. 3 öBG einen Spielraum (Kann-Vorschrift) beim Entscheid, ob ein neues Vergabeverfahren durchgeführt werden soll oder nicht. Es liegt ein Entschliessungsermessen vor, das vom Verwaltungsgericht grundsätzlich nicht überprüft werden darf (§ 30 Abs. 2 öBG). Der Begriff der wesentlich geänderten Leistung stellt hingegen einen unbestimmten Rechtsbegriff dar und kann vom Verwaltungsgericht überprüft werden (Häfelin/Müller, Grundriss des Allgemeinen Verwaltungsrechts, Zürich 1993, Rz. 348, 363 und 368).
c) Im Fall der mengenmässigen Änderung hängt die Wesentlichkeit demnach von einer bestimmten Grenzmenge ab, um welche die Leistung reduziert wird und die im Einzelfall festzulegen ist. Unbestritten ist, dass sich der Preis pro Einheit im Verhältnis zur verlangten Leistungsmenge darstellt. Reduziert sich die Leistungsmenge, steigt im Normalfall der Preis pro Einheit an. Auf welche Berechnungsfaktoren die Unternehmer sich dabei aber genau abstützen, kann im Einzelnen nicht bestimmt werden. Darum kann auch nicht ohne weiteres vorausgesagt werden, wie sich ab einer bestimmten Leistungsreduktion die rein preisliche Rangierung gemäss Offertenöffnung verändert.
Die Beschwerdeführerin führt in ihrer Eingabe vom 17. Februar 2000 aus, die seitens des Beschwerdegegners geltend gemachte Leistungsreduktion, nämlich lediglich 216 m2 (was ca. 20% der Bodenbelagsfläche entspricht; vgl. Ziff. 211.001-251.001 der Angebote), habe als Grund für einen Abbruch (mit anschliessender Neudurchführung) nicht ausgereicht, weshalb dieser zu Unrecht erfolgt sei und im ersten Verfahren der Auftrag an sie hätte vergeben werden müssen. Ungeachtet der Berechnungsmethoden sind sich die Parteien einig, dass sich die verlangte Leistung im zweiten Verfahren um 30%, mindestens jedoch um 20% reduziert hat.
Bei einer Minderung der zu bearbeitenden Flächen um 20% muss vorliegend jedoch das Kriterium der Wesentlichkeit als erfüllt betrachtet werden, womit eine Neudurchführung der Submission als gerechtfertigt erscheint. Die verschiedenen Berechnungsfaktoren können sich bei dieser Menge derart auswirken, dass sich die preisliche Rangierung verändert. Gemäss der Offertöffnung vom 1. September 1999 reichte die Beschwerdeführerin das tiefste Angebot ein. Im Abstand von nur Fr. 51.55 folgte schon die Anbieterin auf dem zweiten Platz. Unter solchen Umständen ist es durchaus denkbar, dass nach einer Neuberechnung der Preise die zweitplatzierte Anbieterin das tiefste Angebot einreicht, ohne dass ein verpöntes Abgebot vorliegt. Im Übrigen haben sich in beschränktem Rahmen auch gewisse Mengen erhöht (vgl. Ziff. 255.001 und Ziff. 211.001 der Angebote) sowie sind Leistungsteile als solche dazugekommen (vgl. Ziff. 112.002 resp. 003 der Angebote), was zusätzlich für die Wesentlichkeit der Änderung und somit für eine gerechtfertigte Neudurchführung des Verfahrens spricht. Unter diesen Umständen ist die Abbruchverfügung des Beschwerdegegners vom 8. Februar 2000 zwecks Neudurchführung der Vergabe nicht zu beanstanden und die Beschwerde vom 17. Februar 2000 in diesem Punkt abzuweisen.