Sachverhalt:
A. N._, geboren 1987, bezieht seit 1. Oktober 1994 eine ordentliche einfache Waisenrente der AHV. Sie beendete ihre Mittelschulausbildung in Israel im Juni 2006. Mit Schreiben vom 14. Mai und 18. Juni 2006 informierte die Mutter von N._ die Schweizerische Ausgleichskasse, Genf (im Folgenden: Ausgleichskasse), ihre Tochter habe im Anschluss an die Mittelschulausbildung den (zweijährigen) obligatorischen Militärdienst in Israel bzw. vorgängig eine neunmonatige Sanitätsausbildung zu absolvieren, und ersuchte um Weiterzahlung der Halbwaisenrente. Mit Verfügung vom 6. Juli 2006 wies die Ausgleichskasse das Gesuch ab, da der militärische Vorkurs als Sanitäterin nicht als Berufsausbildung gelte. Mit Einspracheentscheid vom 22. September 2006 hielt sie an ihrer Verfügung fest.
B. Die hiegegen erhobene Beschwerde der N._ hiess das Bundesverwaltungsgericht mit Entscheid vom 3. September 2008 gut, hob den Einspracheentscheid vom 22. September 2006 auf und erkannte, dass die Waisenrente während der Dauer des Militärdienstes weiterhin auszurichten sowie die bisher aufgelaufene Rente nachzuzahlen sei.
C. Die Ausgleichskasse führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des angefochtenen Entscheides.
N._ lässt auf Abweisung der Beschwerde schliessen; das Bundesverwaltungsgericht verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Im angefochtenen Entscheid werden die Rechtsgrundlagen zum Anspruch auf eine Waisenrente der AHV (Art. 25 Abs. 1 erster Satz AHVG), insbesondere auch derjenige junger Erwachsener während der Ausbildungszeit (<ref-law>) und die hiezu ergangene Rechtsprechung (<ref-ruling> E. 5 b und c S. 43 ff.; <ref-ruling> E. 1 S. 165) zutreffend dargelegt. Darauf wird verwiesen.
2. Streitig ist der Rentenanspruch während der Dauer des an die Mittelschule anschliessenden obligatorischen Militärdienstes.
2.1 Das Bundesverwaltungsgericht erwog, beim zweijährigen Militärdienst der Beschwerdegegnerin handle es sich nicht um eine freiwillige Form des Durchdienens, sondern um einen in voller Länge auch für Frauen obligatorischen Militärdienst. Der Ausbildungsunterbruch sei somit auf äussere Umstände zurückzuführen. Der Militärdienst habe als Ausbildung zu gelten, zumal keine Anhaltspunkte vorlägen, wonach die Versicherte ihre Ausbildung nach Beendigung des Militärdienstes nicht fortsetzen und stattdessen eine Erwerbstätigkeit aufnehmen werde. Soweit die Beschwerdeführerin davon ausgehe, die spätere Weiterführung der Ausbildung müsse als sichere Tatsache feststehen, könne ihr nicht gefolgt werden.
2.2 Demgegenüber bringt die beschwerdeführende Ausgleichskasse vor, der Militärdienst und die damit zusammenhängenden Ausbildungen könnten nicht per se als Ausbildung im Sinne des AHVG angesehen werden. In Würdigung der langen Dauer des von der Beschwerdegegnerin zu absolvierenden Militärdienstes sei nicht abzusehen, ob und wann anschliessend eine Ausbildung fortgeführt oder überhaupt angetreten werde. Bei der Gewährung von Stipendien werde beispielsweise von einem Abbruch des Studiums ausgegangen, wenn die Ausbildung während zwei Jahren nicht fortgeführt werde. Zudem könne der Finanzbedarf während der Dauer des Militärdienstes durchaus in Zweifel gezogen werden, da davon auszugehen sei, dass der Staat während dieses Zeitraumes für den Lebensunterhalt aufkomme.
2.3 Die Beschwerdegegnerin argumentiert, zum einen sei der unmittelbar an die Mittelschulausbildung anschliessende Militärdienst obligatorisch, weshalb die lange Dauer dieses äusseren Umstandes ihr nicht zum Nachteil gereichen könne. Der Paramedical-Kurs, welchen sie im Rahmen der Wehrpflicht absolviert habe, werde auch an den Hochschulen angeboten und sei als Teil der Ausbildung zu betrachten. Schliesslich beabsichtigte sie, im September 2009 an der Universität Zürich ein Medizinstudium aufzunehmen. Die Anmeldung hiezu sei am 4. Dezember 2008 erfolgt und habe nicht früher eingereicht werden können, weil das entsprechende Formular frühestens ein halbes Jahr vor Beginn des Studiums abgegeben werden könne.
3. Die Beschwerdegegnerin legte bereits im vorinstanzlichen Verfahren glaubhaft dar, dass sie mit dem Abschluss der Mittelschule lediglich eine erste Ausbildungsetappe zurückgelegt hat. Dies wird durch die letztinstanzlich ins Recht gelegte Anmeldung zum Medizinstudium vom 4. Dezember 2008 bestätigt, welche zu berücksichtigen ist, da die Vorinstanz diesbezüglich keine Sachverhaltsfeststellungen traf (Art. 105 Abs. 2 in Verbindung mit <ref-law>). Das Gleiche gilt für die Vorbringen in der Vernehmlassung (S. 5 Ziff. 4), womit die Weiterverfolgung der Ausbildung nach Ableistung des Militärdienstes mit überwiegender Wahrscheinlichkeit bevorsteht. Im Übrigen würde die Ansicht der Beschwerdeführerin zu einer stossenden Ungleichbehandlung mit jungen Menschen führen, welche die Möglichkeit haben, ihr Studium vor dem Einrücken in den Militärdienst aufzunehmen. Wann der Dienst geleistet wird, kann somit nicht ausschlaggebend sein. Zwar ist bei Absolvierung des obligatorischen Militärdienstes nach der Immatrikulation an einer Hochschule (oder Aufnahme einer anderweitigen Ausbildung) augenscheinlicher, dass keine rentenrelevante Unterbrechung der Ausbildung stattfindet; doch kann auch im Falle des vorgängig zu leistenden Militärdienstes die erforderliche Kontinuität der Ausbildung angenommen werden, wenn deren Fortsetzung durch den Inhaber des Maturitätsausweises nach Dienstende wahrscheinlich ist. Das ist hier der Fall. Die übrigen Vorbringen der Beschwerdeführerin, insbesondere betreffend den verminderten Geldbedarf von Militärdienstleistenden, vermögen keine Bundesrechtsverletzung durch die Vorinstanz darzutun, umso weniger, als die Ausbildung und damit der Rentenanspruch selbst dann nicht unterbrochen wird, wenn die versicherte Person vorübergehend eine bescheidene Erwerbstätigkeit ausübt (hiezu Urteil H 195/87 vom 28. November 1988 E. 2b).
4. Die unterliegende Beschwerdeführerin trägt die Kosten des Verfahrens (<ref-law>) und hat der Beschwerdegegnerin eine Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2500.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Bundesverwaltungsgericht, Abteilung III, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 28. Januar 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle