Sachverhalt:
A. H._, geboren 1956, ist seit 1. November 1996 der Ausgleichskasse des Kantons Aargau als Selbstständigerwerbende (Krankenpflege) im Haupterwerb angeschlossen (Bestätigung der Sozialversicherungsanstalt des Kantons Aargau vom 25. August 1999). Am 22. Januar 2000 schloss sie mit der Klinik Z._, (heute: Klinik Y._) eine "Auftragsvereinbarung" betreffend "Einsätze als Operationsschwester im Ambulatorium A._, nach Vereinbarung bzw. auf Abruf zur Überbrückung eines personellen Engpasses". Mit zwei Verfügungen vom 21. August 2006 forderte die Ausgleichskasse P._ von der Klinik Y._ Lohnbeiträge nach für die Perioden 1. Januar bis 31. Dezember 2002 in Höhe von Fr. 21'369.05 (Referenz-Nr. 12'454) und vom 1. Januar bis 31. Dezember 2003 in Höhe von Fr. 1'873.80 (Referenz-Nr. 12'453), weil H._ bezüglich ihrer Tätigkeit in der Klinik Z._ den Selbstständigenstatus nicht erfülle. Die hiegegen erhobene Einsprache der H._ als Mitbetroffener wies die Ausgleichskasse am 11. Juli 2007 ab.
Das Verwaltungsgericht des Kantons Aargau, bei welchem H._ gegen einen Entscheid des Steuerrekursgerichtes des Kantons Aargau vom 24. Mai 2007, wonach ihre Tätigkeit für die Klinik Z._ im Jahre 2002 als steuerrechtlich unselbstständige zu qualifizieren sei, hatte Beschwerde erheben lassen, wies diese mit Entscheid vom 7. April 2008 ab.
B. H._ liess gegen den Einspracheentscheid der Ausgleichskasse vom 11. Juli 2007 Beschwerde führen, welche das Versicherungsgericht des Kantons Aargau mit Entscheid vom 12. November 2008 guthiess, den Einspracheentscheid aufhob und feststellte, dass H._ in den Jahren 2002 und 2003 ihrer Beitragspflicht als Selbstständigerwerbende nachgekommen sei.
C. Die Ausgleichskasse P._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des angefochtenen Entscheides.
H._ stellt das Rechtsbegehren, es sei auf die Beschwerde nicht einzutreten; eventualiter sei die Beschwerde vollumfänglich abzuweisen. Das Bundesamt für Sozialversicherungen schliesst auf Gutheissung der Beschwerde. Die Klinik Y._ und die Vorinstanz verzichten auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG) kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Dabei legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Es kann eine - für den Ausgang des Verfahrens entscheidende (vgl. Art. 97 Abs. 1 BGG) - Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder wenn sie auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG; Ausnahme: Beschwerden gemäss Art. 97 Abs. 2 BGG [Art. 105 Abs. 3 BGG]).
2. 2.1 Das Bundesgericht prüft die Eintretensvoraussetzungen von Amtes wegen und mit freier Kognition (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1 S. 99). Die Beschwerdeschrift hat unter anderem die Begehren und deren Begründung mit Angabe der Beweismittel zu enthalten, wobei im Rahmen der Begründung in gedrängter Form darzulegen ist, inwiefern der angefochtene Entscheid Recht verletzt (Art. 42 Abs. 1 und 2 BGG; <ref-ruling> E. 2.1 S. 245 f.). Die Beschwerde ans Bundesgericht ist ein reformatorisches Rechtsmittel (Art. 107 Abs. 2 BGG). Daher darf sich die Beschwerde führende Partei grundsätzlich nicht darauf beschränken, die Aufhebung des angefochtenen Entscheides zu beantragen, sondern sie muss einen Antrag in der Sache stellen. Dabei ist anzugeben, welche Punkte des Entscheides angefochten und welche Abänderungen beantragt werden. Grundsätzlich ist ein materieller Antrag erforderlich. Anträge auf Rückweisung der Sache an die Vorinstanz zu neuer Entscheidung oder blosse Aufhebungsanträge genügen nicht und machen die Beschwerde unzulässig, es sei denn, das Bundesgericht wäre im Fall der Beschwerdegutheissung nicht in der Lage, in der Sache selbst zu entscheiden (<ref-ruling> E. 1.3, 133 III 489 f. E. 3.1). Das Begehren kann sich auch aus der Begründung in der Rechtsschrift ergeben (Urteil 8C_3/2009 vom 8. Mai 2009 E. 1).
2.2 Die Beschwerdeführerin verlangt lediglich, die Beschwerde sei gutzuheissen und der angefochtene Entscheid aufzuheben. Einen materiellen Antrag stellt sie nicht. Gleichwohl ist aufgrund der Beschwerdebegründung zu ihren Gunsten davon auszugehen, dass sie vor Bundesgericht die Bestätigung ihres Einspracheentscheides verlangt, sodass die Beschwerdeschrift insofern den Anforderungen an das Rechtsbegehren gemäss Art. 42 Abs. 1 BGG genügt und somit darauf eingetreten werden kann. In der Tat wird der Einspracheentscheid ohne weiteres rechtskräftig, wenn der ihn annullierende kantonale Gerichtsentscheid seinerseits letztinstanzlich aufgehoben wird (Art. 61 BGG).
3. 3.1 Streitig ist die beitragsrechtliche Qualifikation der Tätigkeit der Beschwerdegegnerin in der (heutigen) Klinik Y._ in der Zeit vom 1. Januar 2002 bis 31. Dezember 2003. Dabei handelt es sich um eine Rechtsfrage, welche das Bundesgericht mit uneingeschränkter Kognition prüft (Art. 95 BGG; E. 1 hievor).
3.2 Die Vorinstanz hat die Bestimmungen über den massgebenden Lohn, von welchem paritätische Beiträge erhoben werden (Art. 5 Abs. 2 und 14 Abs. 1 AHVG), unter Hinweis auf die Rechtsprechung (<ref-ruling> E. 4 S. 558), und die Grundsätze zur Abgrenzung zwischen selbstständiger und unselbstständiger Erwerbstätigkeit (<ref-ruling> E. 1 S. 162, 122 V 169 E. 3a S. 171, 281 E. 2a S. 283) sowie die Merkmale, bei deren Vorliegen im Regelfall selbstständige Erwerbstätigkeit anzunehmen ist (<ref-ruling> E. 9a S. 170 f.; Urteil des Eidgenössischen Versicherungsgerichts H 77/04 vom 19. Mai 2005), zutreffend dargelegt. Darauf wird verwiesen.
4. 4.1 Das kantonale Gericht erwog, zwar habe die vorinstanzliche Beschwerdeführerin - und letztinstanzliche Beschwerdegegnerin - ihre Tätigkeit in den Räumen der jeweiligen Einsatzklinik ausgeübt und sei, der Natur der Tätigkeit entsprechend, gewissen Anordnungen der Ärzte und anderer an den Operationen beteiligter Personen unterstellt gewesen. Sie habe aber das alleinige unternehmerische Risiko getragen, innert kürzester Zeit einen wichtigen Kunden bzw. Auftraggeber zu verlieren, weil gemäss der zwischen ihr und der damaligen Klinik Z._ abgeschlossenen Auftragsvereinbarung eine Absage von "ad hoc-Absprachen" für beide Parteien bis einen Tag vor dem betreffenden Einsatz vorgesehen und die Auflösung des Auftragsverhältnisses innert Wochenfrist möglich war. Zudem habe nach den Einsatzbedingungen keine Pflicht bestanden, Anfragen der Klinik betreffend Arbeitseinsätze anzunehmen. Auch seien Aufwendungen für Miet- und Nebenkosten der Geschäftslokalitäten, Geschäftsversicherungen, Büroreinigungs- und Werbekosten aktenkundig. Demzufolge könne mit überwiegender Wahrscheinlichkeit davon ausgegangen werden, dass die Versicherte eigenes Kapital einzusetzen und unternehmerisches Risiko zu tragen habe, so dass die massgebenden Faktoren in den fraglichen Jahren 2002 und 2003 eher für eine selbstständige Erwerbstätigkeit sprächen. Diese Qualifikation werde schliesslich auch durch die stark schwankenden Gewinne in den Jahren 2002 bis 2005 gestützt.
4.2 Demgegenüber bringt die Beschwerde führende Ausgleichskasse vor, die Vorinstanz umgehe das Gebot der Würdigung der gesamten Umstände des Einzelfalles. Der angefochtene Entscheid beruhe lediglich auf den "auszugsweisen Ausführungen" der Beschwerdegegnerin, obwohl (bei ganzheitlicher Betrachtungsweise) die Merkmale einer unselbstständigen Erwerbstätigkeit überwögen (zu welcher Auffassung auch das kantonale Verwaltungsgericht in Bezug auf die Steuerveranlagung gelangt sei). Dieser Auffassung schloss sich das BSV an.
5. 5.1 Soweit das Verwaltungsgericht des Kantons Aargau mit Entscheid vom 4. April 2008 die Tätigkeit der Beschwerdegegnerin für die Klinik Z._ im Jahre 2002 als unselbstständige qualifiziert hat, ist dieser Entscheid für die beitragsrechtliche Qualifikation in der AHV nicht präjudizierend, weil sich die (absolute) Verbindlichkeit der Angaben der Steuerbehörden für die Ausgleichskassen (Art. 23 Abs. 4 AHVV) - und die daraus abgeleitete relative Bindung des Sozialversicherungsgerichts an die rechtskräftigen Steuertaxationen - auf die Bemessung des massgebenden Einkommens und des betrieblichen Eigenkapitals beschränkt. Sowohl die beitragsrechtliche Qualifikation als auch die Fragen, ob überhaupt Erwerbseinkommen und gegebenenfalls solches aus selbstständiger oder aus unselbstständiger Tätigkeit vorliegt und ob die Person, die das Einkommen bezogen hat, beitragspflichtig ist, wird von der Bindungswirkung nicht berührt; vielmehr haben die Ausgleichskassen ohne Bindung an die Steuermeldung nach dem Recht der Alters- und Hinterlassenenversicherung zu beurteilen, wer für ein von der Steuerbehörde gemeldetes Einkommen beitragspflichtig ist (<ref-ruling> E. 2c S. 83).
5.2 Im Raum steht nicht ein Statuswechsel der Beschwerdegegnerin. Der Umstand, dass sie ihre Beitragspflicht als im Haupterwerb selbstständige Krankenpflegerin erfüllt, widerspricht einer Erfassung der hier streitigen Entgelte für die Tätigkeit in der (heutigen) Klinik Y._ als massgebender Lohn nicht, da jedes Erwerbseinkommen dahin zu prüfen ist, ob es aus selbstständiger oder aus unselbstständiger Erwerbstätigkeit stammt (<ref-ruling> E. 3b S. 172).
5.3 Die von der Vorinstanz festgestellten, als solche nicht bestrittenen Tatsachen, wonach es der Beschwerdegegnerin gemäss der am 22. Januar 2000 abgeschlossenen Vereinbarung offen steht, Einsätze kurzfristig abzusagen (und dasselbe Recht auch der Klinik zusteht), bei "ad-hoc-Absprachen" ein Rücktrittsrecht bis einen Tag vor dem jeweiligen Einsatz vereinbart wurde und darüber hinaus keine Pflicht zur Annahme von angebotenen Arbeitseinsätzen besteht, können in der Tat auf eine selbstständige Erwerbstätigkeit hindeuten. Diese weder offensichtlich unrichtigen noch auf einer Rechtsverletzung beruhenden Sachverhaltsfeststellungen sind für das Bundesgericht verbindlich (E. 1 hievor). Indes genügen sie nicht, um den Status der Versicherten abschliessend zu beurteilen. Insbesondere darf nicht unberücksichtigt bleiben, dass das Risiko, welches sich im Erfolg der persönlichen Arbeitsbemühungen, d.h. in der Frage erschöpft, ob und in welchem Umfang die Beschwerdegegnerin mit Einsätzen für die Klinik Y._ rechnen konnte, kein Verlustrisiko einer Selbstständigerwerbenden darstellt. Es liegt eher ein Arbeitsverhältnis auf Abruf vor, was nichts an der Unselbstständigkeit ändert (Urteil H 7/03 vom 30. April 2004, in SVR 2005 AHV Nr. 3, E. 3.3). Zwar war die Beschwerdegegnerin nicht verpflichtet, Aufträge entgegenzunehmen, doch konnten gemäss Vertrag längerfristige Einsätze vereinbart werden, die alsdann einzuhalten waren. Ebenso gilt es zu beachten, dass die Beschwerdegegnerin im Hinblick auf die hier zu beurteilenden Einsätze für die Klinik Y._ nicht nur weisungsgebunden und arbeitsorganisatorisch abhängig war, sondern auch keine beträchtlichen Investitionen zu tätigen oder Angestelltenlöhne zu bezahlen brauchte und demzufolge keine Einbusse von Substanzverlusten zu befürchten hatte, selbst wenn sie infolge selbst getätigter Absagen oder fehlender Angebote von Seiten der Klinik weniger oder keine Einsätze mehr leisten konnte (vgl. Urteil H 296/92 vom 24. November 1993 E. 3 i.f. mit Hinweis). Soweit im angefochtenen Entscheid diese Tatsachen nicht berücksichtigt werden, fehlt es nach den zutreffenden Vorbringen der Beschwerdeführerin einer rechtsgenüglichen Beweiswürdigung, weshalb das Bundesgericht insoweit an die vorinstanzlichen Erwägungen nicht gebunden ist.
5.4 Die Beschwerdegegnerin hat ihre Tätigkeit unbestrittenermassen in den Räumen der Klinik Y._ ausgeübt und dabei deren Infrastruktur (Operationsbesteck, Geräte etc.) benützt. Es leuchtet daher nicht ein, weshalb die in den Erfolgsrechnungen der Jahre 2002 und 2003 (sowie in den weiteren Jahren 2004 und 2005) angeführten Aufwendungen für Miet- und Nebenkosten für die Ausübung der fraglichen Tätigkeit nötig gewesen wären; diese waren allenfalls für die weiteren, als Selbstständigerwerbende beabsichtigten oder tatsächlich erbrachten Tätigkeiten erforderlich. Mit Blick auf die Rechtsprechung zur beitragsrechtlichen Qualifikation von Tätigkeiten im Spitalbereich, wonach beispielsweise sowohl die Honorare der Chefärzte, Co-Chefärzte und leitenden Ärzte für die stationäre Behandlung von Patienten in Privatabteilungen (in den Heilanstalten des Kantons Luzern; <ref-ruling>) als auch hauptberuflich selbstständige Psychologen hinsichtlich ihrer Supervisionstätigkeit für (die kantonalbernischen) Psychiatriekliniken (hiezu das bereits zitierte Urteil H 296/92) Unselbstständige sind, hält die vorinstanzliche Qualifikation der Tätigkeit als Operationsschwester in der Klinik Y._ als selbstständige vor Bundesrecht nicht stand. Insbesondere die räumliche und organisatorische Freiheit der Beschwerdegegnerin bei der Gestaltung ihrer Tätigkeit war hier in weit erheblicherem Masse eingeschränkt als in den soeben angeführten Fällen (vgl. auch Urteil 2P.145/1995 vom 24. Februar 1998 E. 2c und d). Soweit der Beschwerdegegnerin bekannte Personen mit ähnlicher Tätigkeit beitragsrechtlich anders qualifiziert worden sind, wie sie dies in ihrer Vernehmlassung vorbringt, kann sie hieraus nichts zu ihren Gunsten ableiten (<ref-ruling> E. 6a S. 392).
Nach dem Gesagten überwiegen bei der Tätigkeit der Beschwerdegegnerin in der Klinik Y._ (in den hier zur Diskussion stehenden Jahren 2002 und 2003) die Merkmale unselbstständiger Erwerbstätigkeit, weshalb die Beschwerde gutzuheissen ist.
6. Dem Ausgang des Verfahrens entsprechend sind die Gerichtskosten der unterliegenden Beschwerdegegnerin aufzuerlegen (Art. 66 Abs. 1 BGG). Der obsiegenden Ausgleichskasse steht keine Parteientschädigung zu (Art. 68 Abs. 3 BGG; Urteil 9C_880/2008 vom 12. Mai 2009 E. 4).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Versicherungsgerichts des Kantons Aargau vom 12. November 2008 aufgehoben.
2. Die Gerichtskosten von Fr. 1600.- werden der Beschwerdegegnerin auferlegt.
3. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Aargau und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 28. August 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle