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. 