Sachverhalt: A. Der 1988 geborene B._ beantragte am 28. November 2007 (Eingangsdatum) bei der AHV-Ausgleichskasse des Kantons Graubünden eine Entschädigung für Dienstleistende der Schweizer Armee aufgrund eines entgangenen Monatslohnes von Fr. 6'900.-. Zur Begründung gab er an, er hätte, statt Militärdienst zu leisten, in der Firma X._ AG arbeiten können. Dem Antrag legte er ein Bestätigungsschreiben vom 19. November 2007 der Firma bei. Die Ausgleichskasse wies das Gesuch mit Verfügung vom 16. Januar 2008 ab, weil der Gesuchsteller im Zeitpunkt des Einrückens in die Rekrutenschule im Sommer 2007 als nichterwerbstätige Person gelte. Daran hielt sie auf erhobene Einsprache hin fest (Einspracheentscheid vom 31. Juli 2008). B. Die dagegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 3. Februar 2009 ab. C. B._ erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt, die Erwerbsausfallentschädigung sei für die Zeit vom 24. November 2007 bis 23. April 2008 auf der Basis eines entgangenen Verdienstes von Fr. 6'900.- zu bezahlen. Ausgleichskasse und Vorinstanz schliessen auf Abweisung der Beschwerde. D. Am 23. Dezember 2009 fordert das Bundesgericht das Bundesamt für Sozialversicherungen (BSV) zur Vernehmlassung auf. Diese erging am 25. Januar 2010; das BSV schliesst darin sinngemäss auf Abweisung der Beschwerde. Der Beschwerdeführer äussert sich am 18. Februar 2010 zur Stellungnahme des BSV, wobei er an seinem Standpunkt festhält.