Sachverhalt: A. Die 1939 geborene deutsche Staatsangehörige H._ hat Wohnsitz in Deutschland. Sie bezieht sowohl nach deutschem wie - zufolge zeitweiliger Erwerbstätigkeit in der Schweiz - nach schweizerischem Recht eine Altersrente (im November 2011: monatliche AHV-Rente von Fr. 155.-; monatliches deutsches Altersruhegeld in Höhe von EUR 353.29). Seit dem Jahre 2001 befindet sie sich in einem Pflegeheim in Deutschland und bezieht seit 13. Juli 2001 stationäre Hilfe zur Pflege nach dem zwölften Buch des deutschen Sozialgesetzbuches (SGB XII; Bescheinigung des Kreissozialamtes X._ vom 2. November 2011). Die AOK Gesundheitskasse, Bezirksdirektion Y._ (nachfolgend: AOK), lehnte - in Bestätigung einer Verfügung der AOK Z._ vom 1. Oktober 2007 - eine Aufnahme der H._ in die gesetzliche Krankenversicherung ab (Widerspruchsbescheid vom 26. November 2008). Bereits am 29. August 2007 hatte H._ die Helsana Versicherungen AG, Zürich (nachfolgend: Helsana), um Aufnahme in die obligatorische Krankenpflegeversicherung ersucht, was diese mit Verfügung vom 18. Dezember 2007 ablehnte. Nachdem H._ hiegegen Einsprache erhoben hatte, erliess die Helsana ein ebenfalls ablehnendes Verfügungsrektifikat vom 28. Januar 2008 (bestätigt mit Einspracheentscheid vom 30. Mai 2008). B. H._ liess hiegegen Beschwerde erheben, welche das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 12. Juli 2011 guthiess; es hob den Einspracheentscheid vom 30. Mai 2008 auf und wies die Sache an die Helsana zurück zur Behandlung des Aufnahmegesuches im Sinne der Erwägungen. C. Die Helsana führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des angefochtenen Entscheides sowie die Einladung des Bundesamtes für Sozialversicherungen (BSV) zur Vernehmlassung. H._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei; der Antrag auf Einladung des BSV zur Vernehmlassung sei abzuweisen und es sei ihr die unentgeltliche Rechtspflege zu gewähren. Mit Verfügung vom 11. November 2011 weist das Bundesgericht das Gesuch um Nichteinladung des BSV zur Vernehmlassung ab und setzt diesem gleichzeitig Frist zur Einreichung einer solchen an. Die Vernehmlassung des Bundesamtes, mit welcher die Gutheissung der Beschwerde beantragt wird, geht am 19. Dezember 2011 beim Bundesgericht ein. Die Beschwerdegegnerin nimmt hiezu am 2. Februar 2012 Stellung. 