Sachverhalt:
A. Bund und Kantone wollen die Schwerverkehrskontrollen auf den Hauptverkehrsachsen der Schweiz verstärken und hierfür verschiedene Kontrollzentren schaffen. Gemäss dem im Jahre 2003 überarbeiteten Konzept "Intensivierung der Schwerverkehrskontrollen (Konzept 2003)" des Bundesamts für Strassen (ASTRA) ist auf dem Gelände des Güterbahnhofs Schaffhausen ein mittleres Schwerverkehrskompetenzzentrum (sog. Midi-Zentrum) einzurichten. Kontrolliert werden sollen täglich 40, später 80 Lastwagen, die von der Nationalstrasse A4 via Schönenbergbrücke und Fulachstrasse längs des Güterbahnhofes zum künftigen Zentrum geleitet werden. Das Kontrollzentrum soll auf dem Grundstück Nr. 3124 errichtet werden, das im Miteigentum der Schweizerischen Bundesbahnen (SBB) und der Deutschen Bahn (DB) steht und bisher für den Güterumschlag benutzt wurde. Bauherr des geplanten Zentrums ist der Kanton Schaffhausen im Auftrag des Bundes.
Das ASTRA erteilte am 5. August 2004 dem vom Kanton Schaffhausen für das Kontrollzentrum erarbeiteten Detailprojekt die Genehmigung für die von ihm zu bewilligenden Teile (Anlage und Signalisation). Das kantonale Finanzdepartement stellte hierauf im Namen des Bauherrn bei der Baubehörde der Stadt Schaffhausen das Gesuch um Baubewilligung für eine Fahrzeug-Messstation sowie für vier Container für Büros und WC. Während der öffentlichen Auflage des Baugesuchs erhoben verschiedene Anwohner Einwendungen gegen das Vorhaben. Das Bauinspektorat des Kantons Schaffhausen erklärte diese Einwendungen für unbegründet und erteilte am 11. März 2005 die Baubewilligung für das Schwerverkehrs-Kontrollzentrum.
B. Sämtliche Einwender erhoben gegen die Baubewilligung des Bauinspektorates Rekurs beim Regierungsrat des Kantons Schaffhausen. Dieser trat mit Entscheid vom 7. Juni 2005 mangels Legitimation der Einwender auf den Rekurs nicht ein. Er hielt jedoch im Sinne einer Eventualbegründung fest, dass der Rekurs abzuweisen wäre, wenn auf ihn eingetreten werden könnte.
Die Rekurrenten gelangten hierauf mit Verwaltungsgerichtsbeschwerde an das Obergericht des Kantons Schaffhausen. Das Obergericht hiess die Verwaltungsgerichtsbeschwerde mit Urteil vom 16. Dezember 2005 insofern teilweise gut, als der Regierungsrat auf den Rekurs der Einwender nicht eingetreten war. Es bestätigte jedoch die vom Bauinspektorat am 11. März 2005 erteilte Baubewilligung und gewährte für die Abweichung von der Zonenkonformität eine Ausnahme. Die - reduzierten - Kosten des Beschwerdeverfahrens wurden den Beschwerdeführern überbunden. Ausserdem wies das Obergericht den Regierungsrat an, den Beschwerdeführern für das Beschwerdeverfahren eine Prozessentschädigung in halber Höhe der Vertretungskosten auszurichten.
C. Ehepaar A._, B._ und C._, D._, E._, Ehepaar F._, G._, H._ sowie Ehepaar I._ haben gegen den Entscheid des Obergerichtes des Kantons Schaffhausen sowohl Verwaltungsgerichtsbeschwerde als auch staatsrechtliche Beschwerde erhoben. Mit ihren Beschwerden verlangen die Beschwerdeführer die Aufhebung des angefochtenen Entscheides und damit der erteilten Bau- sowie der Ausnahmebewilligung.
Der Regierungsrat des Kantons Schaffhausen stellt den Antrag, auf die staatsrechtliche Beschwerde sei mangels Legitimation der Beschwerdeführer nicht einzutreten. Eventuell sei die Beschwerde abzuweisen oder nur insoweit gutzuheissen, als die Aufhebung der - nicht erforderlichen - Ausnahmebewilligung verlangt worden sei. Im Verfahren der Verwaltungsgerichtsbeschwerde ersucht der Regierungsrat ebenfalls um Nichteintreten mangels Legitimation der Beschwerdeführer; eventuell sei die Verwaltungsgerichtsbeschwerde abzuweisen, soweit darauf einzutreten sei. Das Obergericht stellt sinngemäss Antrag auf Abweisung der staatsrechtlichen Beschwerde und der Verwaltungsgerichtsbeschwerde, soweit auf diese einzutreten sei. Das Bauinspektorat des Kantons Schaffhausen hat sich nicht vernehmen lassen.
Das Bundesamt für Umwelt (BAFU) stellt in seiner Vernehmlassung fest, dass der Entscheid des Obergerichtes bundesrechtskonform sei. Das Bundesamt für Raumplanung (ARE) hat auf eine Stellungnahme verzichtet. Den Parteien ist Gelegenheit gegeben worden, sich zur Stellungnahme des BAFU zu äussern.
Die Gesuche der Beschwerdeführer um Gewährung der aufschiebenden Wirkung der Beschwerden sind mit Präsidialverfügung vom 7. März 2006 abgewiesen worden.

Das Bundesgericht zieht in Erwägung:
1. Die von den Beschwerdeführern eingereichten beiden Beschwerden richten sich gegen den selben Entscheid des Schaffhauser Obergerichtes und sind daher in einem einzigen Urteil zu behandeln.
2. Der Regierungsrat des Kantons Schaffhausen bestreitet in seiner Vernehmlassung in erster Linie, dass die beschwerdeführenden Nachbarn im kantonalen Verfahren überhaupt beschwerdebefugt gewesen seien. Die durch den Betrieb des Schwerverkehrs-Kontrollzentrums verursachten Auswirkungen seien nicht als eigenständige Belastung feststellbar. Der Lärm der zum Kontrollzentrum zufahrenden und von diesem wegfahrenden Lastwagen gehe im allgemeinen Strassenlärm unter. Die Kontrolltätigkeit selbst führe zu keinen Emissionen. Im Weiteren könne von einer Beeinträchtigung der Aussicht keine Rede sein und sei fraglich, ob die aufzustellenden Container vom nächstgelegenen Grundstück der Beschwerdeführer aus überhaupt gesehen werden könnten. Das Obergericht hätte daher auf die Beschwerde der Anwohner gar nicht eintreten dürfen.
Diese Einwendung ist vorweg zu prüfen.
2.1 Das Obergericht hat zu Recht ausgeführt, dass die Kantone verpflichtet sind, bei der Anwendung von Bundesverwaltungsrecht, insbesondere von eidgenössischem Umweltschutzrecht sowie bei der Anwendung von eidgenössischem und kantonalem Raumplanungsrecht, die Rechtsmittelbefugnis mindestens im gleichen Umfang wie für die Verwaltungsgerichtsbeschwerde an das Bundesgericht zu gewähren (vgl. Art. 98a Abs. 3 OG in der Fassung vom 4. Oktober 1991, Art. 33 Abs. 3 lit. a des Bundesgesetzes über die Raumplanung vom 22. Juni 1979 [Raumplanungsgesetz, RPG; SR 700]). Der angefochtene Entscheid beruht, jedenfalls zum Teil, auf solchem Bundesverwaltungsrecht. Das Bundesgericht kann sich mithin zunächst darauf beschränken zu untersuchen, ob die Beschwerdeführer im Sinne von Art. 103 lit. a OG als beschwerdebefugt betrachtet werden durften oder ob ihnen - wie der Regierungsrat geltend macht - die Beschwerdelegitimation hätte abgesprochen werden müssen.
2.2 Nach Art. 103 lit. a OG ist zur Verwaltungsgerichtsbeschwerde berechtigt, wer durch die angefochtene Verfügung berührt ist und ein schutzwürdiges Interesse an deren Aufhebung oder Änderung hat. Fechten - wie hier - nicht die Verfügungsadressaten, sondern Dritte die Verfügung an, so wird zur Abgrenzung gegenüber der unzulässigen Popularbeschwerde verlangt, dass die Beschwerdeführer durch den angefochtenen Entscheid stärker als die Allgemeinheit betroffen sind und in einer besonderen, beachtenswerten, nahen Beziehung zur Streitsache stehen (<ref-ruling> E. 1, 121 II 176 E. 26, je mit Hinweisen auf weitere Urteile). Diese Nähe der Beziehung muss bei Bauprojekten insbesondere in räumlicher Beziehung gegeben sein; allerdings vermag eine bloss örtliche Nähe für sich allein noch keine besondere, beachtenswerte Beziehung zum Streitgegenstand zu begründen.
Das Interesse von Dritten an der Aufhebung oder Änderung der Verfügung kann rechtlicher oder auch bloss tatsächlicher Natur sein, doch muss es sich um eigene, persönliche Interessen der Beschwerdeführer handeln; öffentliche Interessen allein oder die Interessen anderer Dritter können nicht angerufen werden. Das Interesse der Beschwerdeführer gilt als schutzwürdig, wenn ihre tatsächliche oder rechtliche Situation durch den Ausgang des Verfahrens unmittelbar beeinflusst werden kann, d.h. wenn sie durch das Beschwerdeverfahren einen materiellen oder ideellen Nachteil von sich abwenden oder aus diesem einen praktischen Nutzen ziehen können (vgl. etwa <ref-ruling> E. 2, 125 I 7 E. 3a, mit Hinweisen auf Lehre und Rechtsprechung).
2.3 Es ist unbestritten, dass einzelne Liegenschaften der Beschwerdeführer in unmittelbarer Nähe des für das Projekt beanspruchten Areals des Güterbahnhofes liegen und nur durch die Fulachstrasse von diesem getrennt werden. Vom Regierungsrat wird auch eingeräumt, dass der Betrieb des Kontrollzentrums zu täglich 80 bzw. 160 zusätzlichen Lastwagen-Fahrten auf der Fulachstrasse führen wird. Nun trifft zwar zu, dass die durch die zusätzlichen Fahrten bedingte Lärmmehrbelastung, wird sie gemäss den Vorschriften der Lärmschutz-Verordnung gemittelt bzw. auf die ganze Tages- oder Nachtzeit bezogen (vgl. Anhang 3 der Lärmschutz-Verordnung vom 15. Dezember 1986 [LSV, SR 814.41]), als solche kaum feststellbar ist. Dies ändert jedoch nichts daran, dass einzelne Vorbeifahrten von den Anwohnern wahrgenommen werden und unter Umständen störend wirken können. Zudem werden die Beschwerdeführer Sichtverbindung mit dem Kontrollzentrum haben, wenn auch grössere Teile der rund 6 m unterhalb der Fulachstrasse zu errichtenden Anlagen durch die Strassenmauer abgedeckt werden dürften. Im Weiteren ist nicht auszuschliessen, dass die Installation der Anlagen mit gewissen Störungen für die Nachbarschaft verbunden sein wird. Eine solche faktische Betroffenheit genügt aber, um eine Beschwerdelegitimation im Sinne von Art. 103 lit. a OG - und somit auch für das bundesgerichtliche Verfahren - zu bejahen. Da die Beschwerdeführer eine gemeinsame Rechtsschrift eingereicht haben, kann offen bleiben, ob die Beschwerdebefugnis allen Beteiligten zuzuerkennen ist.
3. Die Beschwerdeführer haben nicht nur Verwaltungsgerichtsbeschwerde erhoben, sondern auch staatsrechtliche Beschwerde eingereicht. Die staatsrechtliche Beschwerde wegen Verletzung verfassungsmässiger Rechte ist nur gegeben, wenn die behauptete Rechtsverletzung nicht sonstwie durch Klage oder Rechtsmittel beim Bundesgericht oder einer anderen Bundesbehörde gerügt werden kann (Art. 84 Abs. 2 OG). Die staatsrechtliche Beschwerde ist hier daher unzulässig, soweit der Entscheid des Obergerichtes mit Verwaltungsgerichtsbeschwerde angefochten werden kann.
3.1 Umstritten ist die Bewilligung für die Errichtung eines Schwerverkehrs-Kontrollzentrums in der Stadt Schaffhausen. Kantonale Bauentscheide über Bauten im Baugebiet unterliegen nach Art. 34 Abs. 3 RPG grundsätzlich der staatsrechtlichen Beschwerde. Sie können jedoch nach bundesgerichtlicher Rechtsprechung insoweit mit Verwaltungsgerichtsbeschwerde angefochten werden, als geltend gemacht wird, es sei Bundesverwaltungsrecht, insbesondere eidgenössisches Umweltschutzrecht, umgangen oder solches nicht richtig angewendet worden. Weiter können gemischtrechtliche Verfügungen ebenfalls mit Verwaltungsgerichtsbeschwerde angefochten werden, soweit Anordnungen in Frage stehen, die in Anwendung übrigen kantonalen Rechts ergangen sind, das einen hinreichend engen Sachzusammenhang mit den zu beurteilenden Fragen des Bundesverwaltungsrechts aufweist. Soweit dagegen dem angefochtenen Entscheid selbständiges kantonales Recht ohne den genannten Sachzusammenhang zum Bundesrecht zugrunde liegt, steht ausschliesslich die staatsrechtliche Beschwerde zur Verfügung (vgl. <ref-ruling> E. 1; Urteile 1A.5/1999 vom 29. Juni 1999 E. 2b, publ. in URP 1999 S. 800, und 1A.216/2003 vom 16. März 2004 E. 1, publ. in URP 2004 S. 349; s.a. <ref-ruling> E. 1).
3.2 Die Beschwerdeführer rügen mit Verwaltungsgerichtsbeschwerde die Nichtanwendung der eidgenössischen Nationalstrassengesetzgebung und damit zusammenhängend die Verletzung der Pflicht, eine formelle Umweltverträglichkeitsprüfung durchzuführen. Nach ihrer Auffassung sind auch weitere Bestimmungen des Umweltschutzgesetzes vom 7. Oktober 1983 (Umweltschutzgesetz, USG; SR 814.01) missachtet worden. In der staatsrechtlichen Beschwerde wird im Wesentlichen beanstandet, dass das Obergericht selbst die Ausnahmebewilligung erteilt und die Angelegenheit nicht an die Baubewilligungsbehörde zurückgewiesen hat. Darin liege eine Verletzung der in Art. 17 der Schaffhauser Kantonsverfassung (KV/SH) verankerten Rechtsweggarantie und eine Verweigerung der vollen Überprüfung durch eine Beschwerdebehörde im Sinne von Art. 33 Abs. 3 lit. b RPG. Weiter wird willkürliche Anwendung der Bestimmungen von Art. 51 und 57 des kantonalen Gesetzes über die Raumplanung und das öffentliche Baurecht im Kanton Schaffhausen vom 1. Dezember 1997 (BauG) geltend gemacht. Schliesslich bezeichnen die Beschwerdeführer die vom Obergericht getroffene Kosten- und Entschädigungsregelung als willkürlich.
Die Vorbringen, mit denen Verfahrensgarantien sowie das Willkürverbot angerufen werden, stehen mit den gerügten Verletzungen von Bundesverwaltungsrecht nicht in engem Zusammenhang. Sie sind somit zu Recht mit staatsrechtlicher Beschwerde vorgetragen worden. Die eingereichte staatsrechtliche Beschwerde erweist sich grundsätzlich als zulässig.
4. Zu behandeln ist zunächst die Verwaltungsgerichtsbeschwerde. Erwiese sie sich als begründet, wäre der angefochtene Entscheid ohne weiteres aufzuheben und das Bauprojekt dem Nationalstrassenrecht zu unterstellen.
Die Beschwerdeführer bringen gleich wie im kantonalen Verfahren als Hauptargument vor, die Schwerverkehrs-Kontrollzentren bildeten nach Art. 3 lit. n der Verordnung über die Nationalstrassen vom 18. Dezember 1995 (NSV; SR 725.111) notwendigerweise Bestandteil der Nationalstrassenanlagen und unterstünden daher dem Nationalstrassenrecht. Für das hier umstrittene Vorhaben hätte somit ein Ausführungsprojekt erarbeitet und dieses gemäss Anhang Ziffer I/11 zur Verordnung über die Umweltverträglichkeitsprüfung vom 19. Oktober 1988 (UVPV; SR 814.011) einer Umweltverträglichkeitsprüfung unterzogen werden müssen.
Das Obergericht hat sich mit diesem Einwand im angefochtenen Entscheid eingehend befasst und insbesondere darauf hingewiesen, dass die in Art. 3 NSV aufgezählten Bauteile nicht zwingend Bestandteile der Nationalstrassen sein müssten, sondern den Nationalstrassenanlagen nur "je nach ihrer Ausbauform und den von der technischen Funktion her bedingten Erfordernissen" zuzurechnen seien. Die in Art. 3 lit. n genannten Zentren für Schwerverkehrskontrollen bildeten daher Bestandteile der Nationalstrasse, wenn sie in deren Bereich erstellt würden. Werde aber ein solches Zentrum räumlich getrennt vom Nationalstrassennetz errichtet, müsse es - auch im Hinblick auf die verfassungsmässige Aufteilung der Aufgaben von Bund und Kantonen im Strassenwesen - zulässig sein, dieses dem kantonalen Baubewilligungsverfahren zu unterstellen.
Diese Erwägungen des Obergerichtes, die hier nur im Wesentlichen wiedergegeben werden und auf die im Sinne von Art. 36a Abs. 3 OG insgesamt verwiesen werden kann, sind zutreffend und stehen mit dem Sinn und Zweck der Nationalstrassengesetzgebung in keinerlei Widerspruch. Eine Missachtung des Nationalstrassenrechts ist nicht ersichtlich. Demnach ist auch die Pflicht zur Durchführung einer formellen Umweltverträglichkeitsprüfung zu Recht verneint worden, wird doch eine solche - was auch die Beschwerdeführer nicht behaupten - für Projekte wie das vorliegende im kantonalen Recht nicht verlangt.
5. In luftreinhalterechtlicher Hinsicht machen die Beschwerdeführer geltend, dass die Zuführung von zusätzlichem Schwerverkehr in das stark vorbelastete Gebiet rund um die Fulachstrasse vermieden werden müsse.
Es wird von niemandem in Abrede gestellt, dass das Schwerverkehrs-Kontrollzentrum in einem lufthygienisch teilweise übermässig belasteten Gebiet errichtet werden soll, für welches im Rahmen eines Massnahmenplanes Vorkehren zur Verminderung oder Beseitigung der Einwirkungen vorzusehen sind (vgl. Art. 11 Abs. 3 und Art. 44a USG; Art. 9 Abs. 4, Art. 19 und Art. 31 ff. der Luftreinhalte-Verordnung vom 16. Dezember 1985 [LRV; SR 814.318.142.1]). Im angefochtenen Entscheid wird hierzu ausgeführt, der Kanton Schaffhausen habe im Jahre 1990 einen solchen Massnahmenplan erlassen und im Jahre 1999 Bilanz gezogen. Die Massnahmenplanung sehe für den Strassenverkehr besondere Massnahmen vor, die allerdings nicht darin bestünden, auf Strassen wie der Fulachstrasse neue emittierende Anlagen auszuschliessen oder den Schwerverkehr zu beschränken oder zu verbieten. Es könne sich daher lediglich die Frage stellen, ob eine solche Anordnung auch ohne Grundlage im Massnahmenplan getroffen werden könnte. Ein solches wäre nach bundesgerichtlicher Rechtsprechung jedoch nur möglich, wenn neue oder wesentlich geänderte Anlagen im Streite lägen, die mit überdurchschnittlichen Emissionen verbunden sind. Dies sei aber vorliegend nicht der Fall, führe doch der Betrieb des Schwerverkehrs-Kontrollzentrum lediglich zu 80 bzw. 160 zusätzlichen Lastwagen-Fahrten pro Tag, während nach der Verkehrszählung 2003 die Fulachstrasse täglich von über 11'000 Motorfahrzeugen, davon knapp 900 Lastwagen, befahren werde. Die Voraussetzungen für isoliert angeordnete verschärfte Emissionsbegrenzungen seien somit nicht gegeben. Das Obergericht ist deshalb zum Schluss gelangt, dass die lufthygienische Sanierung im Bereich der Fulachstrasse im Rahmen der ordentlichen - und zu ergänzenden - Massnahmenplanung erfolgen müsse. Das Bundesamt für Umwelt teilt diese Meinung. Was die Beschwerdeführer unter Berufung auf <ref-ruling> gegen diese Auffassung einwenden, ist schon deshalb unbehelflich, weil es in jenem Fall - im Gegensatz zu hier - um einen überdurchschnittlichen Emittenten ging. Die Verwaltungsgerichtsbeschwerde erweist sich auch in dieser Hinsicht als unbegründet.
6. Die Beschwerdeführer bestreiten vor Bundesgericht nicht mehr, dass der mit dem Betrieb des Kontrollzentrums verbundene Lastwagenverkehr den Lärmpegel im Gebiet Fulachstrasse nur un- oder kaum merkbar ansteigen lassen wird. Sie weisen indes darauf hin, dass die "ideelle Immission durch die 80 zusätzlichen 28- oder 40-Tönner" unberücksichtigt geblieben sei, legen jedoch in keiner Weise dar, aus welchen Normen sich ein entsprechender Abwehranspruch ergäbe. Auf die Verwaltungsgerichtsbeschwerde kann insofern mangels einer genügenden Begründung im Sinne von Art. 108 Abs. 2 OG nicht eingetreten werden.
7. Zur staatsrechtlichen Beschwerde ist - im Gegensatz zur Verwaltungsgerichtsbeschwerde - nur berechtigt, wer durch den angefochtenen Entscheid in seinen rechtlich geschützten Interessen beeinträchtigt ist. Die Erteilung einer Baubewilligung kann deshalb von den Eigentümern benachbarter Grundstücke bloss angefochten werden, wenn sie die Verletzung von Bauvorschriften geltend machen, die ausser den Interessen der Allgemeinheit auch oder in erster Linie dem Schutz der Nachbarn dienen. Von den beschwerdeführenden Nachbarn ist ebenfalls darzutun, dass sie sich im Schutzbereich dieser Vorschriften befinden und durch die behaupteten widerrechtlichen Auswirkungen der Bauten betroffen werden (vgl. <ref-ruling> E. 1a, 119 Ia 362 E. 1b;<ref-ruling> E. 1c S. 442 f., je mit Hinweisen). Unabhängig von der Legitimation in der Sache selbst können die Verfahrensbeteiligten einen Entscheid auch wegen Verletzung von Verfahrensgarantien anfechten, deren Missachtung eine formelle Rechtsverweigerung darstellt (<ref-ruling> E. 3b S. 167; <ref-ruling> E. 1.4 S. 222, 129 II 297 E. 2.3 S. 301).
Die eingereichte staatsrechtliche Beschwerde enthält keine Ausführungen darüber, ob und inwiefern die angerufenen kantonalen Normen über das Baubewilligungsverfahren auch dem Nachbarschutz dienten und sich die Beschwerdeführer tatsächlich im Schutzbereich dieser Normen befänden. Einzugehen ist daher allein auf die Vorbringen über die Verletzung von Verfahrensgarantien. Dazu zählt vor allem die Rüge, das Obergericht habe durch die Erteilung einer Ausnahmebewilligung im letztinstanzlichen Verfahren verhindert, dass diese Verfügung - insbesondere mit freier Kognition - überprüft werden könne; darin lägen Verstösse gegen Art. 17 KV/SH und Art. 33 Abs. 3 lit. b RPG. Weiter wird geltend gemacht, die Erteilung der Ausnahmebewilligung sei ohne sachliche Begründung und in Verletzung des rechtlichen Gehörs erfolgt.
7.1 Der Vorwurf der Verletzung von Art. 17 KV/SH und Art. 33 Abs. 3 lit. b RPG ist erstmals vor Bundesgericht erhoben worden und somit unzulässig (vgl. Art. 86 Abs. 1 OG). Die Beschwerdeführer hätten denn auch im obergerichtlichen Verfahren durchaus Gelegenheit gehabt, die Beachtung dieser Bestimmungen zu fordern:
Den Beschwerdeführern ist im obergerichtlichen Verfahren mit Schreiben des Instruktionsrichters vom 24. November 2005 mitgeteilt worden, das Obergericht sehe vor, die Sache auch materiell zu behandeln. Dabei ist darauf hingewiesen worden, dass sich im Rahmen der Rechtsanwendung von Amtes wegen die Frage stelle, ob allenfalls gestützt auf Art. 51 BauG eine Ausnahmebewilligung erteilt werden könne. Die Parteien sind aufgefordert worden, sich zu dieser Frage zu äussern. Die Beschwerdeführer haben in einer ausführlichen Stellungnahme vom 15. Dezember 2005 bestritten, dass die materiellen Voraussetzungen für die Erteilung einer Ausnahmebewilligung gegeben seien, jedoch nicht geltend gemacht, dass die Gewährung der Ausnahmen im obergerichtlichen Verfahren mit Art. 17 KV/SH und Art. 33 Abs. 3 lit. b RPG unvereinbar wäre. Auf die im staatsrechtlichen Verfahren neu erhobenen Einwendungen ist nicht einzutreten.
7.2 Die genannten Rügen wären übrigens abzuweisen, wäre auf sie einzutreten:
Art. 17 Abs. 1 KV/SH garantiert "bei Rechtsstreitigkeiten Anspruch auf Beurteilung durch ein kantonales Gericht", spricht sich aber weder über den einzuhaltenden Instanzenzug noch über die Befugnis der Gerichte aus, in den Streitigkeiten selbst neu oder nur kassatorisch zu entscheiden. Die gerichtliche Beurteilung der Rechtsstreitigkeit hat hier aber stattgefunden.
Art. 33 Abs. 3 lit b RPG gewährleistet die "volle Überprüfung" von raumplanungsrechtlichen Verfügungen "durch wenigstens eine Beschwerdeinstanz". Diese volle Überprüfung hat im regierungsrätlichen Beschwerdeverfahren stattgefunden. Zwar ist der Regierungsrat im Ergebnis auf den Rekurs der Nachbarn mangels Legitimation nicht eingetreten, hat aber deren Einwendungen materiell behandelt und als unbegründet erkannt. Dass das Obergericht schliesslich die Baubewilligung auf eine erweiterte Rechtsgrundlage abgestützt hat, ändert nichts daran, dass eine volle Überprüfung im Sinne des bundesrechtlichen Erfordernisses vorgenommen worden ist.
7.3 Aus dem Gesagten ergibt sich auch, dass der Entscheid, die für das Bauvorhaben nötigen Ausnahmen zu gewähren, nach Anhörung der Parteien getroffen worden ist. In der Urteilsbegründung wird weiter im Einzelnen dargelegt, weshalb sich das Obergericht zum Entscheid in der Sache selbst berechtigt hält und inwiefern hier eine Sondersituation gegeben sei, welche die Gewährung einer Ausnahmebewilligung gemäss Art. 51 BauG rechtfertige. Die Vorwürfe der Verweigerung des rechtlichen Gehörs und der mangelnden sachlichen Begründung sind offensichtlich haltlos.
8. Die Beschwerdeführer gehen bei ihrer Beanstandung der Kosten- und Entschädigungsregelung davon aus, dass sich das Obergericht mit der Gutheissung der Beschwerden hinsichtlich der Legitimation hätte begnügen und die Sache selbst an die untere Instanz zurückweisen müssen. Da den Beschwerdeführern in dieser Frage, soweit überhaupt auf sie einzugehen ist, nicht gefolgt werden kann, stösst die Kritik am Kosten- und Entschädigungsentscheid ins Leere.
9. Zusammenfassend ist festzuhalten, dass die Verwaltungsgerichtsbeschwerde und die staatsrechtliche Beschwerde abzuweisen sind, soweit auf sie eingetreten werden kann.
Die bundesgerichtlichen Kosten sind dem Ausgang der Verfahren entsprechend den Beschwerdeführern aufzuerlegen (Art. 156 Abs. 1 OG). Parteientschädigungen sind im Hinblick auf Art. 159 Abs. 2 OG nicht zuzuerkennen.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit auf sie einzutreten ist.
2. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit auf sie einzutreten ist.
3. Die Gerichtsgebühr von insgesamt Fr. 5'000.-- wird den Beschwerdeführern auferlegt.
4. Dieses Urteil wird den Beschwerdeführern, dem Kanton Schaffhausen, dem Bauinspektorat, dem Regierungsrat und dem Obergericht des Kantons Schaffhausen sowie dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 1. November 2006
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: