Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid des Verwaltungsgerichts in öffentlich-rechtlichen Angelegenheiten.
1.1 Der angefochtene Entscheid bestätigt einen Rückweisungsentscheid der Regierung, mit dem die Gemeinde angewiesen wurde, die Baubewilligung für die gesamte Anlage, einschliesslich der UMTS-Antennen, zu erteilen. Das Baubewilligungsverfahren ist somit noch nicht abgeschlossen, weshalb es sich formell um einen Zwischenentscheid handelt. Allerdings besteht keinerlei Entscheidungsspielraum mehr für die Gemeinde: Diese ist an die Erwägungen des Rückweisungsentscheids gebunden und muss daher das Baugesuch (gemäss nachträglich eingereichtem Grundrissplan vom 15. November 2004) samt UMTS-Antennen bewilligen. Die Rückweisung dient damit nur noch der Umsetzung des oberinstanzlich Angeordneten. In dieser Konstellation ist der Rückweisungsentscheid einem Endentscheid i.S.v. <ref-law> gleichzustellen (Urteil 9C_684/2007 vom 27. Dezember 2007 E. 1.1 mit Hinweisen, in: SVR 2008 IV Nr. 39 S. 131; Felix Uhlmann, in: Basler Kommentar zum Bundesgerichtsgesetz, N 9 zu Art. 90).
1.2 Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat, durch den angefochtenen Entscheid oder Erlass besonders berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat. (<ref-law>).
1.2.1 Alle Beschwerdeführer wohnen innerhalb eines Perimeters, in dem die Strahlung der projektierten Mobilfunkanlage bis zu 10% des Anlagegrenzwerts erreichen kann (sog. Einspracheperimeter; vgl. <ref-ruling> E. 2.3 und 2.4 S. 171 f.). Die Beschwerdeführer 1-10 haben überdies rechtzeitig Einsprache erhoben und sich am gesamten kantonalen Verfahren beteiligt, weshalb sie in der Sache zur Beschwerde befugt sind. Gleiches gilt (entgegen dem Vorbringen der Beschwerdeschrift) für die Beschwerdeführer 14 und 15 (vgl. Rekursentscheid E. 4d S. 8 oben).
1.2.2 Die Beschwerdeführer 12 und 13 hatten nicht fristgemäss Einsprache erhoben, weshalb die Vorinstanzen lediglich auf ihre formellen, nicht aber auf ihre materiellen Rügen eingetreten sind. Diese Beschwerdeführer sind daher auch vor Bundesgericht grundsätzlich nur zur Beschwerde befugt, soweit sie Verfahrensverletzungen rügen und namentlich geltend machen, dass sie aufgrund von Mängeln bei der Publikation des Baugesuchs gehindert worden seien, rechtzeitig Einsprache zu erheben.
1.2.3 Auf die Beschwerde des Beschwerdeführers 11 ist das Verwaltungsgericht nicht eingetreten, weil dieser nicht Rekurs an das Departement geführt habe und deshalb nicht formell beschwert sei. Der Beschwerdeführer beantragt die Aufhebung des Nichteintretensentscheids (wozu er grundsätzlich legitimiert ist), begründet diesen Antrag aber nicht näher. Insofern ist auf seine Beschwerde nicht einzutreten (Art. 106 Abs. 2 i.V.m. <ref-law>).
1.3 Mit diesen Massgaben ist auf die Beschwerde einzutreten.
2. Die Beschwerdeführer rügen zunächst, das Baugesuch sei lediglich im offiziellen Anschlagkasten der damaligen Gemeinde Krummenau, im Ortsteil Neu St. Johann, publiziert worden, nicht aber in der damaligen Gemeinde Nesslau und in den anderen Ortsteilen der Gemeinde Krummenau. Zwar sei das Bauvorhaben auch visiert worden; die Visiere seien jedoch für einen grossen Teil der betroffenen Personen, namentlich im Ortsteil Schlatt der Gemeinde Nesslau (der ebenfalls im Einspracheperimeter liege), nicht sichtbar gewesen. Hierfür beantragen sie die Durchführung eines Augenscheins. Eine Publikation im amtlichen Publikationsorgan der Obertoggenburger Gemeinden, namentlich in den Toggenburger Nachrichten, sei nicht erfolgt.
Die Beschwerdeführer sind der Auffassung, dies verletze den Anspruch auf rechtliches Gehör (<ref-law>), weshalb die Publikation und öffentliche Auflage des Baugesuchs hätte wiederholt werden müssen. In diesem Fall hätten die Beschwerdeführer 12 und 13 rechtzeitig Einsprache erhoben; zudem hätten weitere Personen aus dem Weiler Schlatt Einsprache erheben können. Die Beschwerdeführer weisen darauf hin, dass der Gemeinderat Krummenau am Augenschein vom 19. August 2003 den Vorwurf der ungenügenden Publikation akzeptiert und Weisung erteilt habe, in Zukunft alle Bauten und Anlagen mit grösseren Auswirkungen im Amtsblatt auszuschreiben.
2.1 Fraglich ist zunächst, inwiefern noch ein schutzwürdiges Interesse an der Behandlung dieser Rüge besteht, nachdem alle Beschwerdeführer noch während des Einspracheverfahrens Kenntnis vom Baugesuch erhalten haben, an der Einspracheverhandlung der Gemeinde (persönlich oder durch ihren damaligen Anwalt) vertreten waren und ihr gemeinsamer Rekurs bzw. ihre Beschwerde von der Regierung bzw. vom Verwaltungsgericht auch in der Sache behandelt worden ist. Allerdings ist einzuräumen, dass die Beschwerdeführer 12 und 13 im Falle der beantragten Rückweisung der Sache an das Verwaltungsgericht wissen müssen, ob sie zur Teilnahme am weiteren Verfahren berechtigt sind oder nicht; zudem wirkt sich die Frage auch auf den bundesgerichtlichen Kostenentscheid aus (vgl. unten, E. 5).
2.2 Art. 12b des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451) sieht vor, dass Verfügungen, gegen welche die Verbandsbeschwerde offen steht, den beschwerdeberechtigten Organisationen schriftlich mitgeteilt oder im kantonalen Publikationsorgan veröffentlicht werden (Abs. 1). Sieht das kantonale Recht (wie hier) ein Einspracheverfahren vor, so muss schon das Baugesuch auf diese Weise eröffnet werden (Abs. 2).
Im vorliegenden Fall ist aufgrund der Akten (Gesuch für Bauten und Anlagen ausserhalb der Bauzonen) davon auszugehen, dass das Baugesuch den beschwerdeberechtigten Verbänden angezeigt worden ist; jedenfalls wird dies von den Beschwerdeführern nicht bestritten. Insofern konnte die Publikation im kantonalen Amtsblatt unterbleiben.
2.3 Ansonsten bestimmt sich die Publikation eines Baugesuchs nach kantonalem Recht. Dieses muss allerdings gewährleisten, dass alle potentiell vom Baugesuch Betroffenen orientiert werden und somit die Möglichkeit haben, das rechtliche Gehör wahrzunehmen (<ref-law>).
Nach der bundesgerichtlichen Praxis genügt der Aushang von Baugesuchen am Anschlagbrett der Gemeinde auch in grösseren Gemeinden, wenn sie von einer anderen Massnahme der Bekanntmachung begleitet wird, wie insbesondere der Profilierung (<ref-ruling> E. 3a S. 24 f.; kritisch Gerold Steinmann, St. Galler Kommentar zur BV, 2. Aufl., Art. 29 N 24).
Art. 82 des St. Galler Baugesetzes vom 6. Juni 1972 (BauG) sieht vor, dass das Baugesuch Anstössern (d.h. Grundeigentümern, deren Grundstück nicht mehr als 30 Meter von der geplanten Baute oder Anlage entfernt ist), mit eingeschriebenem Brief zur Kenntnis zu bringen ist; Baugesuch und Unterlagen sind während vierzehn Tagen zur Einsicht aufzulegen, wobei die Auflage während der Einsprachefrist durch öffentlichen Anschlag bekannt zu machen ist. Bevor das Baugesuch eingereicht wird, müssen Visiere aufgestellt werden, welche Stellung und Ausmass der Baute oder Anlage bezeichnen (Art. 81 Abs. 1 BauG).
Regierung und Verwaltungsgericht haben dargelegt, dass der An-schlag und die Profilierung den Anforderungen des kantonalen Rechts genügten. Die Beschwerdeführer bringen nichts vor, was diese Erwägungen willkürlich erscheinen liesse.
2.4 Den Beschwerdeführern ist allerdings einzuräumen, dass die Profilierung zur Bekanntmachung des Baugesuchs ungenügend sein kann, wenn eine Anlage weiträumige Immissionen verursacht und deshalb auch Personen berührt, die in relativ grosser Entfernung vom Baugrundstück wohnen und die Profilierung deshalb möglicherweise nicht wahrnehmen werden.
Im vorliegenden Fall ist unstreitig, dass die Profilierung im Weiler Schlatt (der damaligen Gemeinde Nesslau) nicht sichtbar war, dessen Bewohner zur Einsprache gegen die Mobilfunkanlage berechtigt gewesen wären. Es erübrigt sich deshalb, hierfür einen Augenschein durchzuführen.
Allerdings stammen die Beschwerdeführer alle aus dem Weiler Ennetbühl (der damaligen Gemeinde Krummenau). Am Augenschein des Departements vom 20. August 2004 wurde festgehalten, dass der oberste Teil des Antennenmasts und die Visierverlängerung von 8.2 m stellenweise einsehbar waren; dies wird von den Beschwerdeführern nicht bestritten. Damit war für die Beschwerdeführer erkennbar, dass ein neues Baugesuch für den Standort "im Brüggli" (wo bereits in den Jahren 2001 und 2002 Mobilfunkanlagen bewilligt, aber nicht realisiert worden waren) aufgelegt werden würde. Sie hätten somit die Möglichkeit gehabt, sich durch Einsicht in die Auflageakten über das Bauvorhaben zu informieren und rechtzeitig Einsprache zu erheben. Insofern ist ihnen kein Nachteil entstanden und ihr rechtliches Gehör nicht verletzt worden. Dies gilt insbesondere auch für die Beschwerdeführer 12 und 13.
Soweit Dritte (namentlich im Ortsteil Schlatt) nicht genügend orientiert und deshalb vom Einreichen einer Einsprache abgehalten worden sein sollten, hätten diese die Wiederherstellung der Einsprachefrist verlangen oder Rechtsmittel ergreifen müssen, sobald sie vom Baugesuch bzw. der Baubewilligung Kenntnis erhalten hatten (<ref-ruling> E. 2c S. 220; <ref-ruling> E. 2b/cc S. 180).
2.5 Nach dem Gesagten verletzt der Entscheid des Verwaltungsgerichts, der die Publikation für rechtskonform erachtete, nicht das rechtliche Gehör der Beschwerdeführer.
3. Weiter rügen die Beschwerdeführer eine Verletzung des rechtlichen Gehörs, weil die Standortdatenblätter während des laufenden Bewilligungsverfahrens zweimal ausgetauscht und nicht öffentlich aufgelegt worden seien.
3.1 Das Verwaltungsgericht ging davon aus, es handle sich um einen Mangel von geringfügiger Bedeutung, der von der Regierung - die eine umfassende Kognition ausgeübt habe - als geheilt erkannt werden konnte.
3.2 Diese Auffassung ist verfassungsrechtlich nicht zu beanstanden: Es entspricht ständiger bundesgerichtlicher Praxis, dass nicht besonders schwerwiegende Verletzungen des rechtlichen Gehörs geheilt werden können, wenn die betroffene Person die Möglichkeit erhält, sich vor einer Beschwerdeinstanz zu äussern, die sowohl den Sachverhalt als auch die Rechtslage mit mindestens gleicher Kognition prüfen kann wie die Vorinstanz (<ref-ruling> E. 5.1 S. 390 mit Hinweisen), auch wenn dies zwangsläufig zum Verlust einer Instanz führt. Nachträgliche Korrekturen von Standortdatenblättern wurden ausnahmsweise - sofern es sich um Änderungen von untergeordneter Bedeutung handelt und alle Beteiligten dazu Stellung nehmen konnten - sogar noch im Verfahren vor Bundesgericht zugelassen (vgl. als Beispiel <ref-ruling>).
Im vorliegenden Fall fehlte im ersten Standortdatenblatt der bestehende Polizeifunksender, was im zweiten Standortdatenblatt nachgeholt wurde. Im dritten wurden die Neigungen der Antennen leicht modifiziert (Verzicht auf die Angabe von Winkelbereichen für die vertikale Senderichtung) und eine falsche Höhenangabe (OMEN Nr. 7) korrigiert. Die Sendeleistung der Antennen sowie der Radius des Anlage- und Einspracheperimeters blieben in allen drei Blättern unverändert. Die berechneten Immissionswerte weisen nur geringfügige Abweichungen auf und liegen jeweils deutlich unter den Anlagegrenzwerten. Die von den Beschwerdeführern als bedeutend eingestufte Änderung bei OMEN Nr. 7 beruht auf der Korrektur der Höhendifferenz und wirkt sich zugunsten der Anlieger aus, beträgt doch die NIS-Belastung nur noch 0.93 V/m (anstatt 1.82 V/m gemäss 2. Standortdatenblatt). Die Beschwerdeführer erhielten im Rekursverfahren Gelegenheit, die neuen Unterlagen einzusehen und konnte sich dazu äussern.
3.3 Insofern durfte das Verwaltungsgericht davon ausgehen, der Mangel sei schon von der Regierung geheilt worden. Zutreffend ist allerdings die Kritik des BAFU, wonach das erste Standortdatenblatt schon im Zeitpunkt seiner Einreichung veraltet war und unverständlich ist, weshalb nicht von Anfang an das zweite Standortdatenblatt (das vom 2. April 2003 datiert und damit schon vor Einreichung des Baugesuchs erstellt wurde) öffentlich aufgelegt worden ist.
4. Das Bauvorhaben ist in der Landwirtschaftszone unstreitig nicht zonenkonform. Das AREG erteilte die Ausnahmebewilligung gestützt auf Art. 24c RPG. Diese Bestimmung ist jedoch - wie bereits die Regierung in ihrem Entscheid (E. 9 S. 14 f.) dargelegt hat - nicht anwendbar: Zum einen war der Antennenmast schon im Zeitpunkt seiner Errichtung zonenwidrig, ist also nicht durch die nachträgliche Änderung von Erlassen oder Plänen zonenwidrig geworden (vgl. Art. 41 der Raumplanungsverordnung vom 28. Juni 2000 [RPV; SR 700.1]); zum anderen soll die bestehende Polizeifunkantenne nicht massvoll erweitert werden: Vielmehr sollen ein neuer (grösserer) Mast mit 16 neuen Antennen für GSM- und UMTS-Mobilfunk und ein zusätzlicher Gerätecontainer errichtet werden.
Die Regierung wie auch das Verwaltungsgericht hielten das Vorhaben dagegen nach Art. 24 RPG für bewilligungsfähig. Dies wird von den Beschwerdeführern bestritten und ist im Folgenden zu prüfen.
4.1 Nach dieser Bestimmung kann eine Ausnahmebewilligung erteilt werden, wenn der Zweck der Bauten und Anlagen einen Standort ausserhalb der Bauzonen erfordert (lit. a) und keine überwiegenden Inte-ressen entgegenstehen (lit. b).
Antennen für den Mobilfunk können nach der Rechtsprechung ausnahmsweise auf einen Standort ausserhalb der Bauzonen angewiesen sein, wenn eine Deckungs- oder Kapazitätslücke aus funktechnischen Gründen mit einem oder mehreren Standorten innerhalb der Bauzonen nicht in genügender Weise beseitigt werden kann bzw. es bei einem Standort innerhalb der Bauzonen zu einer nicht vertretbaren Störung der in anderen Funkzellen des Netzes verwendeten Frequenzen kommen würde. Nicht ausreichend sind dagegen wirtschaftliche Vorteile des gewählten Standorts (z.B. geringere Landerwerbskosten; voraussichtlich geringere Zahl von Einsprachen) oder zivilrechtliche Gründe für die Standortwahl, wie z.B. die Weigerung von Eigentümern, einer Mobilfunkantenne auf ihren Grundstücken innerhalb der Bauzonen zuzustimmen (Urteile 1A.186/2002 vom 23. Mai 2003 E. 3.1, in: ZBl 105/2004 S. 103; RDAF 2005 I S. 591; 1A.120/2006 vom 12. Februar 2007 E. 3.1, in: URP 2007 S. 827; RDAF 2008 I S. 564).
In zwei jüngeren Entscheiden hat das Bundesgericht diese Rechtsprechung präzisiert für Mobilfunkanlagen, die auf bestehende Bauten und Anlagen, wie namentlich Hochspannungs- und Antennenmasten, montiert werden. Hier kann die Standortgebundenheit auch dann bejaht werden, wenn diese zwar nicht aus funktechnischen Gründen unentbehrlich, sich aber im Rahmen einer konkreten Interessenabwägung als wesentlich geeigneter erweisen als mögliche Standorte innerhalb der Bauzone. Voraussetzung ist, dass die Mobilfunkanlage ausserhalb der Bauzonen keine erhebliche Zweckentfremdung von Nichtbauzonenland bewirkt und nicht störend in Erscheinung tritt. Dies ist grundsätzlich nur an Örtlichkeiten möglich, an denen sich bereits zonenkonforme oder zonenwidrige Bauten und Anlagen befinden (<ref-ruling> E. 4.3.3 S. 326 f., 409 E. 4.2 S. 417 f.; vgl. auch Urteile 1C_345/2008 vom 29. Januar 2009 E. 2.3 und 1C_14/2008 vom 25. Februar 2009 E. 4.2).
4.2 Regierung und Verwaltungsgericht bejahten die Standortgebundenheit gestützt auf diese neuere Rechtsprechung. Zwar würden die neuen Antennen nicht auf den bestehenden Antennenmast montiert, sondern dieser werde abgebrochen und durch einen neuen, höheren Mast mit grösserem Fundament ersetzt, der etwas weiter vom Wald entfernt erstellt werde; zudem solle zusätzlich zur bestehenden eine neue Gerätekabine vom 6.9 m x 3.3 m erstellt werden. Dennoch bewirke das Bauvorhaben keine erhebliche Zweckentfremdung von Nichtbauzonenland und habe keine wesentlichen Auswirkungen auf dessen Nutzung; die Verschiebung des Standorts erfolge im Interesse des Waldes, um den Baumwurzeln genügend Raum zu gewähren. Die neue Anlage solle die Verbindungsstrasse von Wattwil auf die Schwägalp und die umliegenden Wohngebiete von Krummenau und Ennetbühl mit Mobilfunkdienstleistungen der drei Mobilfunkanbieter versorgen und eine entsprechende Versorgungslücke schliessen. Damit würden auch Gebiete ausserhalb der Bauzonen versorgt. Der gewählte Standort erlaube dank seines erhöhten Standorts eine weitflächige Abdeckung, wodurch weitere Standorte in der Umgebung vermieden werden könnten. Zudem könne derselbe Standort von allen drei Mobilfunkanbietern genutzt werden, was an einem Standort innerhalb der Bauzonen wegen Überschreitung der Immissions- und Anlagegrenzwerte kaum möglich wäre. Der Standort im Brüggli sei den Mobilfunkanbietern vom Gemeinderat im Jahr 2000 empfohlen worden, als dieser sich gegen die Errichtung einer Mobilfunkanlage direkt oberhalb des Dorfs Ennetbühl an einem sehr exponierten Standort ausgesprochen habe. Der gewählte Standort befinde sich an einem Abhang in einer flachen Zwischenebene; talwärts werde die Anlage zu einem grossen Teil vom Wald abgedeckt und trete deshalb nicht störend in Erscheinung.
4.3 Die Beschwerdeführer bestreiten den Bedarf für die neuen Antennen, nachdem die in den Mobilfunkkonzessionen enthaltenen Auflagen bezüglich Abdeckung schon bei Weitem erfüllt seien. Es sei nicht nachgewiesen, dass eine Deckungs- oder Kapazitätslücke bestehe, die nicht in genügender Weise innerhalb der Bauzonen beseitigt werden könne. Weiter sei zu berücksichtigen, dass die Mobilfunkanlage nicht auf der bestehenden Anlage angebracht werde, sondern eine vollständig neue Anlage errichtet werde, mit einem Mast von 29.2 m Höhe (statt bisher 21 m) und einer Gerätekabine, die dreimal so gross sei wie üblich (weil für drei Mobilfunkanbieter konzipiert). Weder der Mast noch die Gerätekabine hielten den gesetzlichen Waldabstand von 15 m ein. Unter diesen Umständen seien keine besonders wichtigen und objektiven Gründe ersichtlich, die den vorgesehenen Standort gegenüber anderen Standorten in der Bauzone als viel vorteilhafter erscheinen liessen.
4.4 Auch das ARE ist der Auffassung, dass es am Nachweis einer Versorgungslücke fehle; insbesondere befänden sich in den Akten keinerlei Abdeckungskarten. Sogar die als Parteibehauptung zu wertende Standortbegründung der Orange vom 22. September 2003 wecke eher Zweifel am Bestehen einer Versorgungslücke, insbesondere bezüglich eines Teils der Wohngebiete Krummenau und Ennetbühl. Überdies werde mit der gewählten Lösung (massive Vergrösserung des Antennenfundaments; neue Gerätekabine) signifikant mehr Nichtbauzonenland in Anspruch genommen, als wenn die neuen Antennen am alten Antennenmast angebracht würden; insofern sei die Situation mit jener in <ref-ruling> nicht vergleichbar. Schliesslich seien keine Alternativen an bestehenden oder neuen Standorten in den Bauzonen geprüft worden. Solche Abklärungen seien jedoch unerlässlich, wenn die Standortgebundenheit ausserhalb der Bauzonen mit dem Argument bejaht werden solle, dieser Standort sei viel vorteilhafter als mögliche Standorte innerhalb der Bauzonen. Es sei konstante Praxis, dass kein Anspruch darauf bestehe, eine Mobilfunkantenne ausserhalb der Bauzone zu erstellen, nur weil mehrere Mobilfunkbetreiber innerhalb der Bauzonen - sei es aus funktechnischen oder aus anderen Gründen - keinen Standort finden, an welchem sie eine einzige gemeinsame Antennenanlage erstellen können.
4.5 Die Einwände der Beschwerdeführer und des ARE sind berechtigt.
Das Verwaltungsgericht hat keinerlei Ausführungen zum Vorliegen einer Versorgungslücke gemacht; die Regierung verwies hierfür lediglich auf das Schreiben der Orange vom 22. September 2003. Aus diesem Schreiben ergibt sich jedoch, dass allen drei Mobilfunkbetreibern vor Kurzem ein Standort auf der Schwägalp bewilligt worden ist und die Wohngebiete von Krummenau und Ennetbühl schon heute - wenn auch aus einiger Distanz und damit nicht optimal - mit Mobilfunk versorgt sind. Die angebliche Versorgungslücke für die Verbindung in Richtung Ebnat-Kappel/Wattwil wurde nicht näher substantiiert (z.B. mit Abdeckungskarten). Insofern hätte Anlass bestanden, Bestehen und Ausmass der Versorgungslücke näher abzuklären.
Anders als in den oben zitierten Bundesgerichtsentscheiden beansprucht die hier geplante Anlage in nicht unerheblichem Umfang Nichtbauzonenland: einerseits durch das neue, grössere Fundament, andererseits durch die neue, rund 21 m2 grosse Gerätekabine, die zusätzlich zur bestehenden Kabine errichtet werden soll.
Unter diesen Umständen darf die Standortgebundenheit nicht einfach unter Hinweis auf die bestehende bauliche Nutzung des Standorts bejaht werden, sondern es muss geprüft werden, ob sich dieser als klarerweise besser geeignet erweist als mögliche Standorte innerhalb der Bauzonen (vgl. Urteil 1C_345/2008 vom 29. Januar 2009 E. 2.5). Andere Standorte wurden jedoch im vorliegenden Verfahren nicht geprüft. Ob eine solche Prüfung in einem früheren Verfahren erfolgt ist, lässt sich den Bauakten nicht entnehmen und deshalb nicht überprüfen.
5. Nach dem Gesagten verletzt die vorgenommene Standortevaluation Art. 24 RPG. Die Beschwerde der Beschwerdeführer 1-10, 14 und 15 ist daher gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen.
Sollte nach der Wiederholung der Standortevaluation an dem Standort "Brüggli" festgehalten werden, müsste hierfür ein neues Standortdatenblatt eingeholt und den Beschwerdeführern Gelegenheit gegeben werden, dazu Stellung zu nehmen, bevor nochmals entschieden wird. Hierfür kann auf die Vernehmlassung des BAFU verwiesen werden.
Auf die weiteren materiellen Rügen der Beschwerdeführer braucht unter diesen Umständen nicht eingegangen zu werden. Die formellen Rügen der Beschwerdeführer erweisen sich nach dem oben (E. 2 und 3) Gesagten als unbegründet. Die Beschwerde der Beschwerdeführer 12-13 (die ausschliesslich zur Erhebung dieser Rügen legitimiert sind) ist daher abzuweisen. Auf die Beschwerde des Beschwerdeführers 11 ist nicht einzutreten.
Bei diesem Ausgang des Verfahrens rechtfertigt es sich, die Gerichtskosten zu einem Achtel den Beschwerdeführern 11-13 und zu sieben Achteln der privaten Beschwerdegegnerin aufzuerlegen. Diese hat die Beschwerdeführer 1-10, 14 und 15 zu entschädigen (Art. 66 Abs. 1 und Art. 68 BGG). Bei der Festsetzung der Parteientschädigung ist allerdings zu berücksichtigen, dass die Beschwerdeschrift sich sehr ausgiebig mit (im Ergebnis unbegründeten) formellen Rügen befasst und auch die materiellen Ausführungen (wie die Vernehmlassungen der Bundesämter zeigen) und die Replik viel kürzer hätte gefasst werden können. Der geltend gemachte Honoraraufwand erscheint deshalb unangemessen. Für die Entschädigung ist der in Fällen der vorliegenden Art übliche Ansatz zugrunde zu legen.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde des Beschwerdeführers 11 wird nicht eingetreten.
2. Die Beschwerde der Beschwerdeführer 12 und 13 wird abgewiesen.
3. Im Übrigen wird die Beschwerde gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 9. September 2008 aufgehoben. Die Sache wird zu neuer Beurteilung im Sinne der Erwägungen an das Verwaltungsgericht zurückgewiesen.
4. Die Gerichtskosten von Fr. 4'000.-- werden zu einem Achtel (Fr. 500.--) den Beschwerdeführern 11-13 und zu sieben Achteln (Fr. 3'500.--) der Orange Communications SA auferlegt.
5. Die Orange Communications SA hat die Beschwerdeführer 1-10, 14 und 15 für das bundesgerichtliche Verfahren mit insgesamt Fr. 4'000.-- zu entschädigen.
6. Dieses Urteil wird den Parteien, der Politischen Gemeinde Nesslau-Krummenau, der Regierung und dem Verwaltungsgericht des Kantons St. Gallen sowie dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 28. August 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber