Sachverhalt:
A. Die A._ AG ist der Ausgleichskasse der Schweizer Maschinenindustrie, Zürich (im Folgenden: Ausgleichskasse), angeschlossen. Die Revisionsstelle der Ausgleichskasse führte bei der A._ AG am 13. September und 19. November 2004 sowie am 8. Juni 2005 eine Arbeitgeberkontrolle durch. Dabei gelangte sie zur Auffassung, dass es sich bei gewissen Einlagen der A._ AG in die Pensionskasse X._ AG im Jahre 2001 bzw. (seit einem am 1. Januar 2002 erfolgten Namenswechsel) in die Pensionskasse Y._ AG in den Jahren 2002 bis 2004 um massgebenden Lohn handle. Mit Verfügung vom 7. August 2006, bestätigt durch Einspracheentscheid vom 20. November 2006, forderte die Ausgleichskasse von der A._ AG die Nachzahlung paritätischer Beiträge in der Höhe von Fr. 392'719.85 zuzüglich Verwaltungskosten und Verzugszinsen.
B. Die A._ AG erhob hiegegen Beschwerde beim Obergericht des Kantons Schaffhausen. Dieses hiess die Beschwerde mit Entscheid vom 30. November 2007 gut und hob die Verfügung sowie den Einspracheentscheid auf.
C. Das Bundesamt für Sozialversicherungen (BSV) erhebt Beschwerde mit dem Antrag, der Entscheid des Obergerichts sei aufzuheben und die Sache sei an die Ausgleichskasse zurückzuweisen, damit sie die Beiträge unter Berücksichtigung von aArt. 8ter Abs. 1 lit. c AHVV neu festsetze.
Die A._ AG beantragt Abweisung der Beschwerde, die Ausgleichskasse schliesst sich dem Antrag des BSV an. Das Obergericht des Kantons Schaffhausen verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 1 und 2 BGG), sofern die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG).
Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.4 S. 140).
Das Bundesgericht darf nicht über die Begehren der Parteien hinausgehen (Art. 107 Abs. 1 BGG).
2. Die Vorinstanz legt die gesetzlichen Bestimmungen sowie die Rechtsprechung zur Beitragserhebung vom Einkommen aus unselbstständiger Erwerbstätigkeit (Art. 5 Abs. 1 AHVG), zum massgebenden Lohn (Art. 5 Abs. 2 AHVG, Art. 7 lit. q AHVV [in der bis 31. Dezember 2007 anwendbar gewesenen Form] in Verbindung mit Art. 8ter AHVV [ebenfalls in der bis 31. Dezember 2007 gültig gewesenen Fassung], Art. 5 Abs. 4 AHVG [in Kraft gewesen bis 31. Dezember 2007] in Verbindung mit Art. 8 ff. AHVV; <ref-ruling> E. 3.1 S. 156) sowie zum Bezugstermin und -verfahren (Art. 14 Abs. 1 AHVG) zutreffend dar. Darauf wird verwiesen.
Richtig ist insbesondere auch, dass nach Art. 8 lit. a AHVV reglementarische Beiträge des Arbeitgebers an Vorsorgeeinrichtungen, welche die Voraussetzungen der Steuerbefreiung nach dem Bundesgesetz vom 14. Dezember 1990 über die direkte Bundessteuer (DBG; SR 642.11) erfüllen, nicht zum massgebenden Lohn gehören, sofern sie reglementarisch bzw. statutarisch geschuldet, d.h. im Reglement grundsätzlich oder in bestimmtem Zusammenhang vorgeschrieben sind und nicht vom Gutdünken des Arbeitgebers abhängen. Die blosse Zulässigkeit von Einlagen des Arbeitgebers verleiht diesen dagegen nicht den Charakter reglementarischer Beiträge (Urteil H 32/04 vom 6. September 2004, E. 4.3; publiziert in: AHI 2004 S. 253).
3. Der Sachverhalt ist unbestritten. Nach dem Reglement der Pensionskasse X._ AG (hier massgebende Fassung gemäss dem am 15. November 2000 beschlossenen Nachtrag Nr. 1; im Folgenden: Reglementsnachtrag) ist ein vorzeitiger Bezug der Alterspension ab dem zurückgelegten 60. Altersjahr möglich, sofern (unter anderem) die Beendigung des Arbeitsverhältnisses im Einvernehmen mit der Unternehmung erfolgt ist (Art. 18.4 lit. B Reglementsnachtrag). Für den vorzeitigen Bezug kommt in diesem Fall bis zu einem bestimmten Anteil die Pensionskasse auf, die verbleibenden Kosten entfallen auf die Unternehmung (Art. 18.7 Reglementsnachtrag). Streitig ist, ob diese Leistung der Unternehmung an die Pensionskasse unter Art. 8 lit. a AHVV fällt.
4. 4.1 Bei den fraglichen Zahlungen der A._ AG in den Jahren 2002 bis 2004 handelt es sich unbestrittenermassen um Beiträge der Arbeitgeberin an eine Vorsorgeeinrichtung, welche die Voraussetzungen der Steuerbefreiung erfüllen. Weiter sind die Beiträge im Reglement der Pensionskasse vorgesehen. Die Vorinstanz verneinte eine Beitragspflicht der Beschwerdegegnerin und erwog, soweit die Wegleitung des BSV über den massgebenden Lohn (WML) in der AHV, IV und EO in Rz. 2164.1 über Art. 8 lit. a AHVV hinausgehende zusätzliche Bedingungen an die Ausnahme vom massgebenden Lohn knüpfe, könne die Verwaltungsweisung auf den hier zu beurteilenden Sachverhalt keine Anwendung finden.
Demgegenüber bringt das Beschwerde führende Amt vor, die Leistungspflicht der Beschwerdegegnerin hänge allein davon ab, ob sie im konkreten Einzelfall einer vorzeitigen Pensionierung eines Versicherten und damit der Kostenübernahme ausdrücklich zustimme oder nicht. Die vorzeitige Pensionierung sei mit Abschluss dieser individuellen Vereinbarung herbeigeführt und damit die Realisierung des versicherten Risikos ausgelöst worden. Es verhalte sich somit gleich wie in dem in <ref-ruling> beurteilten Fall, weshalb die von der Beschwerdegegnerin geleisteten Beiträge keinen reglementarischen Charakter aufwiesen und damit beitragspflichtig seien.
Demgegenüber bringt das Beschwerde führende Amt vor, die Leistungspflicht der Beschwerdegegnerin hänge allein davon ab, ob sie im konkreten Einzelfall einer vorzeitigen Pensionierung eines Versicherten und damit der Kostenübernahme ausdrücklich zustimme oder nicht. Die vorzeitige Pensionierung sei mit Abschluss dieser individuellen Vereinbarung herbeigeführt und damit die Realisierung des versicherten Risikos ausgelöst worden. Es verhalte sich somit gleich wie in dem in <ref-ruling> beurteilten Fall, weshalb die von der Beschwerdegegnerin geleisteten Beiträge keinen reglementarischen Charakter aufwiesen und damit beitragspflichtig seien.
4.2 4.2.1 Das Eidgenössische Versicherungsgericht hat im bereits erwähnten Urteil H 32/04, E. 4.2.2, ausgeführt, die blosse Zulässigkeit von Einlagen des Arbeitgebers verleihe diesen nicht den Charakter von reglementarischen Beiträgen im Sinne von Art. 8 lit. a AHVV. Dazu sei vielmehr erforderlich, dass das Reglement die Einzahlung (entweder grundsätzlich oder in einem bestimmten Zusammenhang) verlange. In jenem Fall wurde diese Voraussetzung verneint für eine Leistung, die nicht im Vorsorgereglement, sondern in einem Sozialplan festgelegt war.
4.2.2 In <ref-ruling>, auf den sich sowohl die Vorinstanz als auch das Beschwerde führende Amt berufen, hat sich das Bundesgericht erneut zu Art. 8 lit. a AHVV geäussert. In diesem Entscheid ging es um Beiträge, welche der Bund als Arbeitgeber aus Anlass vorzeitiger Pensionierung bei Umstrukturierungen nach Massgabe von Art. 105 Bundespersonalverordnung (BPV; SR 172.220.111.3) an die Pensionskasse des Bundes Publica erbringt. Das Bundesgericht hat dort den Normzweck von Art. 8 lit. a AHVV wie folgt dargelegt: Was der Arbeitgeber gestützt auf - ihm grundsätzlich entzogene, jedenfalls nicht ad hoc im Einzelfall abänderbare - normative Grundlagen zu bezahlen hat, sei es regelmässig, periodisch oder im Fall einer vorzeitigen Pensionierung, soll von der AHV-rechtlichen Beitragspflicht befreit sein (E. 7.4). Es hat sodann darauf hingewiesen, dass im öffentlichen Recht sowohl das Arbeitsverhältnis als auch das Berufsvorsorgeverhältnis oft durch den gleichen Erlassgeber normiert sind. Die zur Diskussion stehende Vorruhestandsregelung liegt bezüglich ihrer Normierung und Anwendung im Einzelfall in der Kompetenz des Bundes als Arbeitgeber, wobei er die Bedingungen der Leistungsausrichtung grundsätzlich jederzeit ändern kann (E. 7.5). Gegen die Annahme reglementarischer Beiträge spricht entscheidend der Umstand, dass die Eidgenossenschaft als Arbeitgeberin frei darüber befindet, welche Arbeitnehmer in einer konkreten betrieblichen Situation vorzeitig pensioniert und welche weiter beschäftigt werden sollen. Entscheidet sich die zuständige Amtsstelle - in Wahrnehmung ihres Führungsauftrages und des ihr dabei zustehenden Gestaltungsspielraumes im Rahmen bundesrätlicher oder departementaler Vorgaben - für die erste Variante, müssen als zwangsläufige Folge dieses Unternehmensentscheides der Publica durch den Bund gestützt auf Art. 105 Abs. 3 BPV die fehlenden Deckungskapitalien erstattet werden. Die Zahlungspflicht erwächst dem Bund mithin nur und erst, weil und nachdem das versicherte Risiko der unverschuldeten Entlassung in Form einseitig angeordneter vorzeitiger Pensionierung schon herbeigeführt worden ist. Demgegenüber meint reglementarische Beiträge im Sinne der Verordnungsbestimmung finanzielle Zuwendungen an die berufliche Vorsorge, welche - wie es deren Wesen als Versicherung entspricht - vor Eintritt der versicherten Risiken verbindlich (durch Vertrag oder Gesetz) festgelegt worden und vom Arbeitgeber während des Vorsorgeverhältnisses oder spätestens im ebenfalls zum Voraus festgelegten künftigen Versicherungsfall zu entrichten sind. Als Beispiel für Beiträge im Sinne von Art. 8 lit. a AHVV nannte das Gericht den Fall, in dem ein Gesamtarbeitsvertrag festlegt, dass die Arbeitnehmer mit 60 Jahren vorzeitig in Pension gehen können und der Arbeitgeber für die Kosten dieser Frühpensionierungen aufkommt. Davon kann aber nicht gesprochen werden, weil der Eidgenossenschaft die Pflicht zur Beitragsleistung erst entsteht, wenn das im Rahmen der weitergehenden beruflichen Vorsorge versicherte Risiko der unverschuldeten Entlassung sich verwirklicht hat. Die Pflicht zur Nachschussleistung nach Art. 105 Abs. 3 BPV ist daher nicht berufsvorsorge- und versicherungsrechtlicher Natur sondern Ausdruck des Versorgungsprinzips, wie es dem öffentlich-rechtlichen Dienstverhältnis zwischen dem Bund und seinen Angestellten in verschiedener Hinsicht zugrunde liegt (E. 7.6).
4.3 Die hier zur Diskussion stehenden Einlagen unterscheiden sich in mehrfacher Hinsicht von den Leistungen, die in den genannten Entscheiden zu beurteilen waren.
4.3.1 Zunächst sind hier im Gegensatz zu dem im Urteil H 32/04 beurteilten Fall - wo entscheidend darauf abgestellt wurde, dass der Sozialplan, welcher die betreffenden Leistungen vorsah, nicht Bestandteil des Vorsorgereglements war, sondern diese in einem Vertrag zwischen Arbeitgeber und Arbeitnehmer vorgesehen waren - die Leistungen des Arbeitgebers im Vorsorgereglement vorgesehen. Die Arbeitgeberin hat sie im Falle einer vorzeitigen Pensionierung zu bezahlen, sofern die im Reglement genannten Voraussetzungen erfüllt sind. Die Leistung der Arbeitgeberin erfolgt somit auf reglementarischer Grundlage in einem bestimmten Zusammenhang, wie es die Rechtsprechung verlangt (vgl. E. 4.2.2 des soeben angeführten Urteils H 32/04).
4.3.2 Anders als bei den in <ref-ruling> beurteilten Beiträgen nach Art. 105 BPV legt die Arbeitgeberin weiter auch nicht zugleich die vorsorgerechtlichen Bestimmungen fest. Diese sind vielmehr im Pensionskassenreglement normiert, welches nicht einseitig durch die Arbeitgeberin, sondern nur durch den paritätisch besetzten Stiftungsrat (Art. 41 und 50 des Reglements; Art. 51 BVG) geändert werden kann.
4.3.3 Schliesslich geht es hier im Unterschied zu <ref-ruling> nicht um einseitige unverschuldete Entlassungen der Arbeitnehmer bei unternehmensbedingten Umstrukturierungen (vgl. Art. 104-106 BPV), sondern um vorzeitige Pensionierungen, welche im Einvernehmen zwischen Arbeitnehmer (in der Regel wohl auf dessen Wunsch) und Arbeitgeberin erfolgen. Leistungen bei vorzeitiger Pensionierung sind vom Normzweck von Art. 8 lit. a AHVV mitumfasst (<ref-ruling> E. 7.4). Die Leistung ist zudem - wie in <ref-ruling> E. 7.5 vorausgesetzt - spätestens beim Eintritt des Versicherungsfalls zu entrichten, der seinerseits zum Voraus festgelegt ist (reglementarische Möglichkeit der Pensionierung mit 60 Jahren, wie in dem in <ref-ruling> E. 7.5 genannten Beispiel).
4.4 Das BSV erblickt eine entscheidende Parallele zu dem in <ref-ruling> entschiedenen Fall darin, dass die Arbeitgeberin auch hier im Einzelfall frei darüber entscheide, wer mit ihrem Einverständnis vorzeitig pensioniert wird. Damit könne sie von Fall zu Fall der Kostenübernahme frei zustimmen oder diese ablehnen, weshalb der Beitrag keinen reglementarischen Charakter im Sinne von Art. 8 lit. a AHVV aufweise.
4.4.1 Es trifft zu, dass das Reglement die Leistungspflicht der Arbeitgeberin vom Einvernehmen zwischen dem Versicherten und der Unternehmung abhängig macht, aber keine Gründe oder Kriterien nennt, nach denen die Arbeitgeberin einer vorzeitigen Pensionierung zuzustimmen hat. Dies ergibt sich indes zwangsläufig aus der Natur der Sache: Ein Einvernehmen zwischen Arbeitgeberin und Arbeitnehmer kann nur im arbeitsvertraglichen Verhältnis zwischen diesen beiden Parteien zustande kommen, welches sowohl vom Vorsorgeverhältnis zwischen Arbeitnehmer und Vorsorgeeinrichtung als auch vom Verhältnis zwischen Arbeitgeberin und Vorsorgeeinrichtung zu trennen ist. Die näheren Umstände eines Einvernehmens können hingegen naturgemäss nicht im Vorsorgereglement normiert werden (<ref-ruling> E. 7.5, S. 561).
4.4.2 Das BSV hat in Rz. 2164.1 WML festgelegt, dass auch Einlagen des Arbeitgebers zum massgebenden Lohn gehören, die zwar vom Reglement der Vorsorgeeinrichtung zwingend vorgeschrieben sind, bei denen aber der Arbeitgeber direkt oder indirekt bestimmen kann, ob bzw. zu Gunsten welcher Personen er sie leisten muss. Die Ausgleichskasse hat sich in ihrer Verfügung auf diese Weisung berufen, die wohl für sie, aber nicht für die Gerichte verbindlich und im Übrigen in der von ihr angeführten Fassung erst ab 1. Januar 2006 gültig ist. Das (auch in die Rz. 2164.1 WML in der seit 1. Januar 2006 gültigen Form aufgenommene) Kriterium, wonach es auf die Entscheidungsfreiheit des Arbeitgebers ankommt, stellt indes eine zusätzliche, in der Verordnung nicht enthaltene Voraussetzung auf (vgl. Art. 8 lit. a AHVV), die sich in dieser Form auch nicht aus der zitierten Rechtsprechung ergibt. Jeder Arbeitgeberbeitrag an eine Vorsorgeeinrichtung ist zwangsläufig Folge des Entscheids des Arbeitgebers, eine Person anzustellen und ihr einen Lohn in bestimmter Höhe zu bezahlen. Es ist somit immer der Arbeitgeber, welcher direkt oder indirekt bestimmt, ob er zu Gunsten bestimmter Personen Einlagen in die Pensionskasse leistet. Demgegenüber hätte die Argumentation des Bundesamtes zur Folge, dass Art. 8 lit. a AHVV toter Buchstabe bliebe, was nicht dem Sinn der Bestimmung entsprechen kann. Auch wenn ein Arbeitsvertrag bereits vorliegt und demzufolge eine Pflicht des Arbeitgebers besteht, den vereinbarten Lohn zu bezahlen, so gibt es doch weiterhin Leistungen, welche der Arbeitgeber freiwillig erbringen kann (Lohnerhöhungen, Boni usw.), und die dann zum versicherten Lohn gehören. Es würde dem Normzweck von Art. 8 lit. a AHVV klar widersprechen, die Pensionskassenbeiträge auf solchen Leistungen von dessen Geltungsbereich deshalb auszunehmen, weil sie auf einen autonomen Entscheid des Arbeitgebers zurückgehen (<ref-ruling> E. 7.4 S. 506 f.).
4.4.3 Für die Anwendung von Art. 8 lit. a AHVV genügt es, dass die Leistung des Arbeitgebers an die Vorsorgeeinrichtung zwingend im Vorsorgereglement verlangt wird, sobald eine bestimmte, im Arbeitsverhältnis begründete Situation vorliegt, unabhängig davon, ob sich diese Situation zwingend aus dem arbeitsrechtlichen Verhältnis ergibt oder ob dem Arbeitgeber ein gewisser Spielraum in ihrer Herbeiführung zusteht. Diese Voraussetzungen sind für die hier streitigen Leistungen erfüllt, zumal diesbezüglich kein Unterschied zwischen laufenden und einmaligen Beiträgen besteht (<ref-ruling> E. 7.3 und 7.4 S. 560 f.; H 32/04 E. 4.2.1 mit Hinweis auf die Erläuterungen des BSV zur Verordnungsänderung vom 16. September 1996 in: AHI 1996 S. 263 ff. [S. 273]; vgl. auch <ref-ruling> E. 3.2 S. 295 ff., 133 V 563 E. 1.2 S. 564). Es handelt sich nicht - wie bei den Leistungen nach Art. 105 BPV - um dienstrechtliche Leistungen an Entlassene bei Umstrukturierungen, welche nur im Rahmen von aArt. 8ter Abs. 1 lit. c AHVV von der Beitragspflicht ausgenommen sind (vgl. <ref-ruling>; <ref-ruling>, nicht publ. E. 8), sondern um vorsorgerechtliche Beiträge im Sinne von Art. 8 lit. a AHVV.
5. Das unterliegende Beschwerde führende Amt trägt keine Kosten (Art. 66 Abs. 4 BGG), hat jedoch der obsiegenden Beschwerdegegnerin eine Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Das beschwerdeführende Amt hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2500.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Schaffhausen und der Ausgleichskasse der Schweizer Maschinenindustrie schriftlich mitgeteilt.
Luzern, 23. Mai 2008
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle