Sachverhalt: A. Der unverheiratete, 1953 geborene C._ war bei der Pensionskasse X._ (im Folgenden: Pensionskasse) berufsvorsorgeversichert, als er im Juli 2007 verstarb. Er hinterliess seine Mutter L._ und drei Schwestern (H._, S._ und R._) als gesetzliche Erbinnen sowie G._ als testamentarische Erbin zu 30 % des Nachlasses und als Vermächtnisnehmerin für den Hausrat und persönliche Gegenstände ohne Anrechnung an den Erbteil. Die Pensionskasse teilte den gesetzlichen Erbinnen mit, es bestehe ein Todesfallkapital von Fr. 431'896.90, welches ihnen gemäss Art. 18 Abs. 5 ihres Reglements zur Hälfte ausbezahlt werde. B. Am 11. Juni 2008 erhob G._ beim Verwaltungsgericht von Appenzell-Ausserrhoden Klage gegen die Pensionskasse mit dem Begehren, es sei das gesamte Todesfallkapital ihr auszubezahlen. Das Verwaltungsgericht lud die vier gesetzlichen Erbinnen zum Verfahren bei und wies die Klage mit Entscheid vom 25. März 2009 ab. C. G._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten erheben mit dem Antrag, unter Aufhebung des Entscheids vom 25. März 2009 sei die Pensionskasse zu verpflichten, ihr das Todesfallkapital von Fr. 431'896.90 zuzüglich Zins auszubezahlen. Die Pensionskasse lässt die Abweisung der Beschwerde beantragen. Die gesetzlichen Erbinnen und das kantonale Gericht lassen sich nicht vernehmen, das Bundesamt für Sozialversicherungen verzichtet auf eine Stellungnahme. 