Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Was das anwendbare Recht betrifft, handelt es sich bei der abgeschlossenen Versicherung ausweislich der vorinstanzlichen Akten um eine KUVG-Zusatzversicherung, wie sie 1996 noch in Geltung stehen konnte. Der Einwand der Beschwerdegegnerin, es liege keine unter <ref-law> fallende Versicherung vor, weil sie nicht vor dem 1. Januar 1996 bestanden habe, sondern auf dieses Datum neu abgeschlossen worden sei, sticht nicht. Es entspricht dem Sinn von <ref-law> und ist auch mit dessen Wortlaut sowohl des Abs. 1 wie des Abs. 2 vereinbar, dass im ersten Jahr nach der Inkraftsetzung des KVG noch Zusatzversicherungen "nach bisherigem Recht" weiter bestehen konnten. Nicht entscheidend ist, ob diese altrechtlichen Versicherungen schon vor dem 1. Januar 1996 bestanden. In diesem Sinne hat das Eidgenössische Versicherungsgericht zu <ref-law> entschieden (RKUV 1998 KV 46 S. 479). Was dort für einen auf den 1. Januar 1996 in Kraft gesetzten und als bestehend im Sinne von <ref-law> qualifizierten Tarifvertrag erwogen wurde, hat auch im Rahmen von <ref-law> seine Richtigkeit. Die Vorinstanz hat die aus der Operation geltend gemachten Ansprüche daher zu Recht anhand des KUVG beurteilt.
2.- Die materiellrechtlichen Grundlagen zur Verschweigung von Krankheiten und zum daraus fliessenden Recht des Versicherers, einen rückwirkenden Vorbehalt anzubringen, wie er hier in Form von "Hallux valgus beidseitig" am 27. November 1996 verfügt wurde, hat die Vorinstanz richtig dargelegt. Darauf kann verwiesen werden.
3.- Das kantonale Gericht hat zur Frage, ob die Beschwerdegegnerin den beidseitigen Hallux valgus (schuldhaft) verschwiegen hat, ein umfangreiches Beweisverfahren durchgeführt. Gestützt darauf ist mit der Vorinstanz eine schuldhafte Verletzung der Anzeigepflicht nicht anzunehmen. Denn es ist entgegen der Beschwerdeführerin auch mit dem im Sozialversicherungsrecht üblichen Beweisgrad der überwiegenden Wahrscheinlichkeit weder bewiesen, noch durch weitere Abklärungsmassnahmen zu beweisen, dass die Beschwerdegegnerin vor dem Versicherungsantrag vom 25. November 1995 nicht nur (nebst weiteren hier nicht interessierenden Befunden am Knie) Spreizfüsse beidseits aufwies, sondern auch eine zu Komplikationen (Ganglienbildung, Bursitiden) führende Valgusfehlstellung, um derentwillen sie am 14. August 1996 operiert wurde. Sämtliche Vorbringen in der Verwaltungsgerichtsbeschwerde vermögen hieran nichts zu ändern. Mithin besteht keine Veranlassung für eine von der vorinstanzlichen Beurteilung abweichende Betrachtungsweise.

Demnach erkennt das Eidg. Versicherungsgericht:
I.Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
II.Es werden keine Gerichtskosten erhoben.
III. Die Beschwerdeführerin hat der Beschwerdegegnerin für das Verfahren vor dem Eidgenössischen Versicherungsgericht eine Parteientschädigung von Fr. 2000. - (einschliesslich Mehrwertsteuer) zu bezahlen.
IV.Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Basel-Stadt und dem Bundesamt für Sozialversicherung zugestellt.
Luzern, 8. November 2000
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der II. Kammer:
Die Gerichtsschreiberin: