Sachverhalt:
A. Die Treuhand X._ AG war von 1960 bis 1997 Revisionsstelle der Pensionskasse Y._ AG (nachfolgend Pensionskasse). In den Jahren 1991 und 1992 tätigte die Pensionskasse Aktienkäufe, welche später Gegenstand rechtlicher Auseinandersetzungen und eines Strafverfahrens wurden. Per Ende 1999 wies die Pensionskasse eine Unterdeckung von rund Fr. 14 Mio. aus und musste liquidiert werden; sie wurde mit Verfügung der Aufsichtsbehörde vom 21. Juli 2000 aufgehoben. Der Sicherheitsfonds BVG verfügte am 17. November 2000, 17. August 2001 und 23. Januar 2002 die "Ausrichtung von Insolvenzleistungen gemäss Art. 25 Abs. 1 und 2 SFV". Bereits am 27. April 2001 hatte die Treuhand X._ AG erklärt, "in Bezug auf eine allfällige Verantwortlichkeitsklage gegen die Treuhand X._ AG auf die Einrede der Verjährung zu verzichten, sofern die Verjährung bis zum heutigen Zeitpunkt nicht eingetreten ist"; alle übrigen Rechte, Einreden und Einwendungen würden vorbehalten.
B. Am 1. Dezember 2008 erhob der Sicherheitsfonds BVG Klage beim Versicherungsgericht des Kantons Aargau gegen die Treuhand X._ AG mit folgendem Rechtsbegehren:
"Die Beklagte sei zu verpflichten, dem Kläger den Betrag von CHF 9'900'000.00 zuzüglich Zins zu 5 % auf CHF 3'000'000.00 seit 20. November 2000 sowie auf CHF 3'000'000.00 seit 20. August 2001 sowie auf CHF 3'900'000.00 seit 25. Januar 2002 zu bezahlen."
Am 23. Januar 2009 erhob die Treuhand X._ AG die Einrede der Verjährung. Das Verfahren wurde in der Folge vorerst auf die Frage der Verjährung beschränkt (Verfügung der Instruktionsrichterin vom 29. Januar 2009).
Im Rahmen des Schriftenwechsels beantragte der Sicherheitsfonds BVG eine Klageerweiterung und führte zur Begründung eine weitere, am 27. Juli 2009 geleistete Zahlung an die Pensionskasse (in Höhe von Fr. 3'856'919.20) an.
Das Versicherungsgericht trat auf die Klageerweiterung nicht ein und wies die Klage zufolge Verjährung ab.
C. Der Sicherheitsfonds BVG führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt, unter Aufhebung des angefochtenen Entscheides sei die Verjährungseinrede der Treuhand X._ AG abzuweisen und die Sache zur Beurteilung der Forderung gemäss vorinstanzlicher Klage an das kantonale Gericht zurückzuweisen. In prozessualer Hinsicht sei der Beschwerde die aufschiebende Wirkung zu erteilen.
Die Treuhand X._ AG schliesst auf Abweisung der Beschwerde und des Antrags um aufschiebende Wirkung. Vorinstanz und Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1. Streitig und zu prüfen ist, ob die Regressforderung des Beschwerde führenden Sicherheitsfonds gegenüber der beschwerdegegnerischen Treuhandgesellschaft bei Klageanhebung am 1. Dezember 2008 verjährt war. Nicht mehr einzugehen ist auf die im vorinstanzlichen Verfahren beantragte Klageerweiterung. Das kantonale Gericht ist hierauf nicht eingetreten und der Beschwerdeführer hat dies in seiner letztinstanzlichen Beschwerde ausdrücklich akzeptiert.
2. 2.1 Die Vorinstanz erwog, die Verjährungsfrist für Forderungen des Sicherheitsfonds regle weder aArt. 56a BVG noch eine andere Norm. Es liege eine echte Gesetzeslücke vor, die vom Gericht modo legislatoris zu schliessen sei. Gestützt auf <ref-ruling> sei von einer fünfjährigen Frist auszugehen, welche jedenfalls unter der bis 31. Dezember 2004 gültig gewesenen Rechtslage mit der Leistungsausrichtung des Sicherheitsfonds zu laufen begann. Vorliegend sei die letzte von insgesamt drei erbrachten Zahlungen vom 25. Januar 2002 fristauslösend gewesen. Demzufolge sei die Verjährung grundsätzlich am 25. Januar 2007 eingetreten. Ob der am 27. April 2001 von der vorinstanzlichen Beklagten (und letztinstanzlichen Beschwerdegegnerin) abgegebene Verjährungsverzicht überhaupt Gültigkeit erlangt habe, könne offen bleiben, weil die Forderung bei Klageanhebung ohnehin verjährt gewesen sei. Der Verjährungsverzicht vom 27. April 2001 sei insofern lückenhaft, als er keine Terminierung enthalte. Diese Lücke müsse nach dem hypothetischen Parteiwillen gefüllt werden, wobei der Sicherheitsfonds nach dem Vertrauensprinzip habe annehmen müssen und dürfen, dass die Treuhandgesellschaft diesen nur bezüglich der für sie günstigeren, kürzeren fünfjährigen Dauer habe abgeben wollen. Der Verzicht habe daher bis 27. April 2006 gedauert und demzufolge keine Auswirkungen auf die am 25. Januar 2007 abgelaufene Verjährungsfrist gehabt. Die Verjährungsverzichtserklärung vom 4. Januar 2007 sei bis 31. Dezember 2007 befristet gewesen und die Verjährung bei Klageerhebung am 1. Dezember 2008 daher bereits eingetreten.
2.2 Der Beschwerdeführer rügt, das kantonale Gericht habe den Sachverhalt offensichtlich unrichtig festgestellt und überdies <ref-law> verletzt, indem es für die Ergänzung der Verzichtserklärung vom 27. April 2001 den nachträglichen Verzicht vom 4. Januar 2007 berücksichtigte, obwohl er selbst dessen Erhalt bestritten und die Beschwerdegegnerin die Strittigkeit der Zustellung ausdrücklich anerkannt habe. Weil die Vorinstanz (primär) auf den "angeblich hypothetischen Willen der Beschwerdegegnerin" abgestellt habe, sei auch die Auslegungsregel verletzt, wonach die Lückenfüllung in erster Linie durch zwingendes Gesetzesrecht, in zweiter Linie durch dispositive Gesetzesbestimmungen erfolgen müsse. Ausgehend von <ref-law> sei die zehnjährige Frist massgeblich, so dass die Forderung bei Klageanhebung noch nicht verjährt gewesen sei. Zu keiner anderen Lösung führe das Vertrauensprinzip, nach welchem er aus der massgeblichen Sicht des Empfängers und mit Blick auf die Funktion des Verjährungsverzichts (Vermeiden einer Betreibung, Wahrung der Kreditwürdigkeit) nicht habe annehmen müssen, die Beschwerdegegnerin sei bei ihrer unbefristeten Verzichtserklärung vom 27. April 2001 von der kürzeren fünfjährigen Frist ausgegangen. Schliesslich handle es sich um eine ausservertragliche Forderung, bei der die Verjährungseinrede schon bei einer sich abzeichnenden Auseinandersetzung abgegeben werden könne; was als ratio legis für <ref-law> angenommen werde, gelte hier nicht.
2.3 Die Beschwerdegegnerin macht geltend, die vorinstanzlichen Erwägungen zur Lückenfüllung seien in keiner Weise zu beanstanden; der Beschwerdeführer selbst sei in seinen vorinstanzlichen Rechtsschriften davon ausgegangen, die Dauer der Verlängerung richte sich im Rahmen der durch <ref-law> auf zehn Jahre begrenzten maximalen Verjährungsfrist nach dem Parteiwillen und verhalte sich widersprüchlich, wenn er letztinstanzlich eine Lückenfüllung nach dem "zwingenden" <ref-law> vertrete. Weil bereits eine Auslegung der Verzichtserklärung nach dem Vertrauensprinzip und weiteren Auslegungsmethoden zum Ziel führe, sei eine gerichtliche Vertragsergänzung nicht mehr notwendig. Es habe für den Beschwerdeführer keinen Grund gegeben, davon auszugehen, sie hätte eine Verlängerung für die maximal zulässige Dauer von zehn Jahren abgeben wollen, zumal seit den angeblich schädigenden Handlungen in den Jahren 1991 und 1992 bereits so viel Zeit verstrichen war. Ob die Verjährungsverzichtserklärung vom 4. Januar 2007 dem Beschwerdeführer zuging, sei nicht relevant, da die darin gewährte Verlängerung bis 31. Dezember 2007 ohnehin vor Klageeinreichung geendet habe. Schliesslich finde die bundesgerichtliche Rechtsprechung, wonach ein Verjährungsverzicht nicht zum Voraus erklärt werden darf, auf alle Verjährungsfristen Anwendung, nicht nur auf vertragliche.
3. Streitig ist, ob der angefochtene Entscheid gegen Bundesrecht verstösst, soweit darin die auf aArt. 56a BVG gestützte Forderung als verjährt erachtet wird.
3.1 In tatsächlicher Hinsicht steht fest und ist unbestritten, dass der Beschwerdeführer am 17. November 2000, 17. August 2001 und 23. Januar 2002 die Zusprechung von Insolvenzleistungen an die Beschwerdegegnerin verfügt hatte. Das kantonale Gericht verstiess nicht gegen Bundesrecht, wenn es den Beginn der Verjährungsfrist für die Regressforderung insgesamt (d.h. betreffend alle drei erfolgten Leistungen) auf den Zeitpunkt der Überweisung der dritten Zahlung vom 25. Januar 2002 festsetzte (<ref-ruling> E. 5.7 S. 171). Ebenfalls steht fest, dass die Beschwerdegegnerin am 27. April 2001 einen unbefristeten Verjährungsverzicht abgab und dass der Beschwerdeführer am 18. Dezember 2006 (somit kurz vor Ablauf von fünf Jahren seit Fristbeginn am 25. Januar 2002) an die Beschwerdegegnerin gelangte und festhielt, er gehe von einer zehnjährigen Verjährungsfrist aus, doch bitte er - sicherheitshalber - um einen weiteren Verjährungsverzicht.
3.2 Der Beschwerdeführer behauptet, die am 4. Januar 2007 von der Beschwerdegegnerin unterzeichnete, bis 31. Dezember 2007 befristete zweite Verzichtserklärung sei ihm nicht zugegangen. Deren Zugang hätte die Beschwerdegegnerin zu beweisen gehabt, weil eine behauptete Tatsache von jener Partei nachzuweisen ist, die daraus ein Recht ableitet (<ref-law>). Die Beschwerdegegnerin hat den Beweis für den Zugang der zweiten Verzichtserklärung aber nicht erbracht, sondern einzig festgehalten, es sei strittig, ob diese beim Beschwerdeführer eingetroffen sei. Weil die beweisbelastete Partei die Folgen trägt, wenn der Beweis nicht erbracht werden kann, ist zu Gunsten des Beschwerdeführers anzunehmen, dass er das entsprechende Schreiben nicht erhielt.
3.3 Die Beschwerdegegnerin hat nach Lage der Akten zu keinem Zeitpunkt, insbesondere auch nicht im Anschluss an das Schreiben vom 18. Dezember 2006, Grund zur Annahme geliefert, sie erachte ihren am 27. April 2001 erklärten Verjährungsverzicht für ungültig und wolle auf die Verjährung nicht (mehr) verzichten. Im Gegenteil unterzeichnete sie - wie erwähnt - am 4. Januar 2007 einen weiteren Verzicht (bis 31. Dezember 2007). Unabhängig davon, ob der zweite Verzicht dem Beschwerdeführer zuging oder nicht, ist somit (auch) nach Beginn der Verjährungsfrist am 25. Januar 2002 von einem zumindest konkludent erklärten Verjährungsverzicht auszugehen. Weil nach dem Gesagten so oder anders eine gültige Verzichtserklärung vorliegt, muss nicht weiter geprüft werden, ob ein Verzicht bereits vor Beginn der Verjährungsfrist abgegeben werden kann.
3.4 Der Beschwerdeführer hatte in seinem Schreiben vom 18. Dezember 2006 festgehalten, unbefristete Verzichtserklärungen würden zwar "von den Gerichten als zehnjährige Verjährungsverzichte gewertet", dennoch bitte er um Unterzeichnung und fristgemässe Rücksendung einer neuerlichen Verzichtserklärung "bis allerspätestens 15. Januar 2007". Der Beschwerdeführer ging somit von einer zehnjährigen Verjährungsfrist aus. Dass er gleichwohl sicherheitshalber eine neuerliche Verzichtserklärung verlangte, zeigt, dass er sich der damals bestehenden Unsicherheiten in Zusammenhang mit der massgeblichen Verjährungsfrist von Regressforderungen bewusst war (hiezu nachfolgende E. 3.5.1). Obwohl gemäss seinen Behauptungen der am 4. Januar 2007 von der Beschwerdegegnerin unterzeichnete Verzicht nie bei ihm einging, blieb er untätig. Dieses Zuwarten ist angesichts der damaligen ungeklärten Rechtslage, seines Problembewusstseins und der Bedeutung der Streitsache nach den zutreffenden Ausführungen der Beschwerdegegnerin unverständlich. Ob dieses Verhalten mit Blick auf die im Geschäftsverkehr gebotene Vorsicht (<ref-ruling> E. 5a S. 336 und 133 III 449 E. 4.1 S. 451) Schutz verdienen könnte, kann aber offen gelassen werden, wenn der am 27. April 2001 erklärte unbefristete Verzicht als zehnjähriger aufzufassen wäre.
3.4 Der Beschwerdeführer hatte in seinem Schreiben vom 18. Dezember 2006 festgehalten, unbefristete Verzichtserklärungen würden zwar "von den Gerichten als zehnjährige Verjährungsverzichte gewertet", dennoch bitte er um Unterzeichnung und fristgemässe Rücksendung einer neuerlichen Verzichtserklärung "bis allerspätestens 15. Januar 2007". Der Beschwerdeführer ging somit von einer zehnjährigen Verjährungsfrist aus. Dass er gleichwohl sicherheitshalber eine neuerliche Verzichtserklärung verlangte, zeigt, dass er sich der damals bestehenden Unsicherheiten in Zusammenhang mit der massgeblichen Verjährungsfrist von Regressforderungen bewusst war (hiezu nachfolgende E. 3.5.1). Obwohl gemäss seinen Behauptungen der am 4. Januar 2007 von der Beschwerdegegnerin unterzeichnete Verzicht nie bei ihm einging, blieb er untätig. Dieses Zuwarten ist angesichts der damaligen ungeklärten Rechtslage, seines Problembewusstseins und der Bedeutung der Streitsache nach den zutreffenden Ausführungen der Beschwerdegegnerin unverständlich. Ob dieses Verhalten mit Blick auf die im Geschäftsverkehr gebotene Vorsicht (<ref-ruling> E. 5a S. 336 und 133 III 449 E. 4.1 S. 451) Schutz verdienen könnte, kann aber offen gelassen werden, wenn der am 27. April 2001 erklärte unbefristete Verzicht als zehnjähriger aufzufassen wäre.
3.5 3.5.1 Es steht fest, dass die am 27. April 2001 abgegebene Verzichtserklärung keine Befristung enthielt und insoweit eine Lücke aufwies. Im hier massgeblichen Zeitraum war die Frage nach der Verjährung von Schadenersatzforderungen des Sicherheitsfonds wie erwähnt noch nicht höchstrichterlich geklärt. Das Bundesgericht hat erst mit <ref-ruling> (vom 16. April 2009) entschieden, dass Haftungs- und Regressansprüche gemäss Art. 56a Abs. 1 BVG in der bis Ende 2004 gültig gewesenen Fassung - in Analogie zu <ref-law> - bereits nach fünf Jahren seit den Leistungen des Sicherheitsfonds verjähren. Es erwog, die angemessene Dauer einer Verjährungsfrist könne nicht unabhängig von der Frage des Fristbeginns festgelegt werden. Weil die für den Fristbeginn massgebliche Erbringung der Leistungen durch den Sicherheitsfonds bedeutend später erfolgt sein könne als das anspruchsbegründende Verhalten, könnten die Schuldner unter Umständen viel später in Anspruch genommen werden als nach Ablauf der maximalen Frist von zehn Jahren seit der Beendigung der schädigenden Handlung. Dies spreche dafür, eine kürzere als die zehnjährige Frist anzunehmen, zumal der Sicherheitsfonds vom Schaden Kenntnis habe, sobald er Zahlungen geleistet habe und es ihm ohne Weiteres zumutbar sei, innert fünf Jahren seit diesem Zeitpunkt Klage zu erheben (BGE a.a.O. E. 5.5. S. 170).
3.5.2 Die Ergänzung einer lückenhaften Willenserklärung hat primär durch dispositives Gesetzesrecht (<ref-ruling> E. 4b S. 488), sekundär durch eine Richterregel zu erfolgen. Es verhält sich anders als bei der Auslegung einer unklaren Willenserklärung, welche als primäres Mittel den Wortlaut kennt und in zweiter Linie die Umstände (in diesem Zusammenhang namentlich auch die Interessenlage der Parteien; vgl. zum Ganzen Gauch/Schluep/Schmid, Schweizerisches Obligationenrecht, Allgemeiner Teil, Band I, 9. Aufl. 2008, Rz. 1205 ff.). Ist eine Willenserklärung lückenhaft, weil kein zwingendes Gesetzesrecht die betreffende Frage regelt, zieht das Gericht somit grundsätzlich zuerst dispositives Gesetzesrecht heran, sodann (selten) Gewohnheitsrecht oder bildet eine eigene Regel (BGE a.a.O.; vgl. auch Gauch/Schluep/Schmid, a.a.O., Rz. 1248). Soweit der vorinstanzliche Entscheid vorrangig auf den hypothetischen Parteiwillen abstellt, hält er vor Bundesrecht nicht stand. Die Lücke in der Erklärung vom 27. April 2001 ist gestützt auf <ref-law> zu schliessen, was bedeutet, dass von einem zehnjährigen Verzicht auf die Einrede der Verjährung auszugehen ist. Im Übrigen könnte die Beschwerdegegnerin selbst dann nicht in guten Treuen davon ausgehen, dass sich der Beschwerdeführer auf eine fünfjährige Frist festlegen wollte, wenn der mutmassliche Parteiwille auszulegen wäre. In seinem Schreiben vom 18. Dezember 2006 machte er deutlich, er suche (nur) vorsichtshalber vor Ablauf von fünf Jahren um eine weitere Verzichtserklärung nach und nehme grundsätzlich an, dass "bei unbefristeten Verzichtserklärungen die Gerichte von einer zehnjährigen Frist ausgingen" (E. 3.4). Die Beschwerde ist somit gutzuheissen. Die Sache geht an die Vorinstanz zurück, damit sie das Verfahren weiterführe.
4. Entsprechend dem Ausgang des Verfahrens sind die Gerichtskosten der unterliegenden Beschwerdegegnerin aufzuerlegen (Art. 65 Abs. 1-3 und <ref-law>). Da mit dem vorliegenden Urteil lediglich die Verjährungsfrage zu prüfen war, rechtfertigt sich eine Gerichtsgebühr am unteren Rand des Tarifs für Streitigkeiten mit Vermögensinteresse (<ref-law>; Art. 1 des Tarifs vom 31. März 2006 für die Gerichtsgebühren im Verfahren vor dem Bundesgericht, SR 173.110.210.1).
Nach <ref-law> wird Behörden oder mit öffentlich-rechtlichen Aufgaben betrauten Organisationen keine Parteientschädigung zugesprochen, wenn sie in ihrem amtlichen Wirkungskreis obsiegen. Dies gilt auch für die Träger oder Versicherer der beruflichen Vorsorge gemäss BVG (<ref-ruling> E. 4a S. 150; Urteil 8C_186/2008 vom 4. November 2008 E. 4.2, nicht publ. in: SVR 2009 UV Nr. 15 S. 60). Vom Grundsatz des fehlenden Parteientschädigungsanspruchs weicht die Rechtsprechung indessen ab, wenn die besondere Art des Prozesses die Zusprechung von Parteikosten rechtfertigt. Eine derartige Ausnahme wird unter anderem in Verfahren um Rückforderungen des Sicherheitsfonds für sichergestellte Leistungen bejaht (Urteil 9C_920/2008 vom 16. April 2009 E. 7 mit Hinweisen auf SVR 2006 BVG Nr. 34 S. 131, B 10/05 E. 10.2; Urteil B 76/01 vom 11. Juli 2002 E. 5b, nicht publ. in: SZS 2003 S. 524).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Versicherungsgerichts des Kantons Aargau vom 1. Juni 2010 aufgehoben. Die Sache wird an die Vorinstanz zurückgewiesen, damit sie über die Klage neu entscheide.
2. Die Gerichtskosten von Fr. 20'000.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 15'000.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Aargau und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 8. Februar 2011
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle