Sachverhalt:
A.
Die E._ AG reichte am 21. Februar 2012 ein Baugesuch ein für den Neubau eines Mehrfamilienhauses mit fünf Wohnungen und einer Einstellhalle auf der in der Wohn- und Gewerbezone WG3 des Ortsteils Feutersoey gelegenen Parzelle Gsteig Gbbl. Nr. 880. Das Regierungsstatthalteramt (RSA) Obersimmental-Saanen bewilligte das Vorhaben mit Gesamtentscheid vom 21. August 2012 und wies die Einsprache der Stockwerkeigentümergemeinschaft STWE A._, von B._, C._ und D._ ab. Dagegen erhoben die Genannten erfolglos Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern (BVE). Das Verwaltungsgericht des Kantons Bern hiess die dagegen erhobene Beschwerde teilweise gut und ergänzte den Gesamtentscheid mit der Auflage, dass die Wohnungen als Erstwohnungen genutzt werden müssten. Das Bundesgericht bestätigte dieses Urteil am 10. Juli 2015 (Urteil 1C_114/2015).
B.
Am 4./18. November 2014 stellte die E._ AG ein neues Baugesuch betreffend dieselbe Parzelle. Das Bauvorhaben umfasst den Neubau eines Wohn- und Gewerbehauses mit einem Unterhalts- und Verkaufsbetrieb für Motorfahrzeuge im Erdgeschoss, drei Erstwohnungen (zwei im Ober- und eine im Dachgeschoss) sowie eine Einstellhalle. Mit Gesamtentscheid vom 25. Juli 2016 bewilligte das Regierungsstatthalteramt Obersimmental-Saanen das Vorhaben mit der Auflage, die Wohnungen als Erstwohnungen zu nutzen, und wies die Einsprache der STWE A._, von B._, C._ und D._ (nachfolgend: die Einsprecher) ab.
Die BVE und anschliessend das Verwaltungsgericht Bern wiesen die dagegen erhobene Beschwerde der Einsprecher ab, soweit sie darauf eintraten.
Mit Urteil vom 15. Juni 2018 (1C_592/2017) hiess das Bundesgericht die Beschwerde der Einsprecher gut und wies die Sache zur Ergänzung des Sachverhalts und neuem Entscheid an das Verwaltungsgericht zurück. Es führte aus, nach der neueren Rechtsprechung sei von Amtes wegen zu prüfen, ob konkrete Indizien vorliegen, welche die Absicht bzw. die Möglichkeit einer Erstwohnungsnutzung des Bauvorhabens als unrealistisch erscheinen lassen.
C.
Das Berner Verwaltungsgericht nahm das Verfahren am 16. Juli 2018 wieder auf und holte verschiedene Unterlagen und Auskünfte ein. Am 2. April 2019 führte es eine öffentliche mündliche Schlussverhandlung durch. Am 7. Mai 2019 wies es die Beschwerde ab, soweit es darauf eintrat.
D.
Dagegen haben die STWE A._, B._, C._ und D._ am 7. Juni 2019 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben. Der Gesamtbauentscheid des Regierungsstatthalteramtes Obersimmental-Saanen vom 25. Juli 2016 und der Entscheid der Bau-, Verkehrs- und Energiedirektion vom 6. Februar 2017 seien nichtig zu erklären bzw. aufzuheben und das Baugesuch der E._ AG vom 20. November 2014 sei abzuweisen. Es sei festzustellen, dass der Gesamtbauentscheid des Regierungsstatthalters Obersimmental-Saanen vom 21. August 2012 erloschen bzw. nichtig sei. Eventualiter sei diese Baubewilligung zu widerrufen. Subsidiär seien die in der Beschwerde beantragten Beweise im bundesgerichtlichen Verfahren abzunehmen.
E.
Die E._ AG (Beschwerdegegnerin), das Verwaltungsgericht und die BVE schliessen auf Abweisung der Beschwerde. Das RSA Obersimmental-Saanen hat auf eine Stellungnahme verzichtet. Der Gemeinderat Gsteig hält an seinen bisher im gesamten Verfahren gemachten Ausführungen fest.
Das Bundesamt für Raumentwicklung (ARE) hält die Beurteilung des Verwaltungsgerichts Bern, wonach für die geplanten Erstwohnungen am vorgesehenen Standort eine Nachfrage existiere, für nachvollziehbar; ein offensichtlicher Rechtsmissbrauch liege nicht vor.
F.
Die Beschwerdeführer haben am 25. November 2019 repliziert.
Es wurde keine Duplik eingereicht.
G.
Mit Verfügung vom 16. Juli 2019 wurde der Beschwerde aufschiebende Wirkung zuerkannt. Das Gesuch um vorsorgliche Massnahmen (Wiederherstellung des ursprünglichen Zustands bzw. Rückbau) wurde abgewiesen.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG).
1.1. Die Beschwerdeführer sind als Eigentümer eines an die Bauparzelle angrenzenden Grundstücks vom Bauvorhaben besonders betroffen und daher zur Beschwerde gegen die Baubewilligung vom 25. Juli 2016 legitimiert (<ref-law>).
Nicht einzutreten ist jedoch auf alle Rügen, die bereits im Urteil 1C_592/2017 vom 15. Juni 2018 beurteilt und nicht zu neuem Entscheid an das Verwaltungsgericht zurückgewiesen worden sind. Darauf kann im vorliegenden Verfahren nicht zurückgekommen werden, ist doch das Bundesgericht - wie zuvor das Verwaltungsgericht - an die Erwägungen des Rückweisungsentscheids gebunden (vgl. <ref-ruling> E. 5.3.3 S. 222; <ref-ruling> E. 2 und 2.1 S. 335; Urteil 1C_325/2018 vom 15. März 2019 E. 4.2). Dies gilt nicht nur für Rügen, die materiell abgewiesen wurden, sondern auch für Rügen, auf welche das Bundesgericht mangels genügender Begründung nicht eingetreten ist (Urteil 1C_592/2017 E. 1.2).
1.2. Die bereits rechtskräftige Baubewilligung vom 21. August 2012 ist nicht Gegenstand des Beschwerdeverfahrens, weshalb auf die sie betreffenden Anträge nicht einzutreten ist. Ihre Nichtigkeit könnte allenfalls vorfrageweise zu prüfen sein, wenn dies für die Beurteilung der vorliegenden Streitsache erforderlich wäre, was jedoch nicht der Fall ist.
1.3. Das Bundesgericht prüft die Auslegung und Anwendung von kantonalem Recht grundsätzlich nur unter Willkürgesichtspunkten, soweit eine solche Rüge in der Beschwerde (und nicht erst in der Replik) vorgebracht und genügend begründet worden ist (Art. 106 Abs. 2 und Art. 42 Abs. 2 BGG). Dafür gelten qualifizierte Begründungsanforderungen (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Wie im Folgenden auszuführen sein wird, genügen gewisse Rügen diesen Anforderungen nicht.
1.4. Mit den erwähnten Vorbehalten ist auf die Beschwerde einzutreten.
2.
Streitig ist in erster Linie, ob die Baubewilligung für drei Erstwohnungen eine Umgehung des Zweitwohnungsverbots gemäss <ref-law> und Art. 6 Abs. 1 Satz 1 des Bundesgesetzes vom 20. März 2015 über Zweitwohnungen (Zweitwohnungsgesetz, ZWG; SR 702) darstellt.
Dies ist eine Frage des Bundesrechts, die das Bundesgericht grundsätzlich von Amtes wegen und frei prüft (<ref-law>). Es legt jedoch den von der Vorinstanz festgestellten Sachverhalt zugrunde, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2.1. Im Urteil 1C_592/2017 vom 15. Juni 2018 führte das Bundesgericht aus, die Möglichkeit, die Erstwohnnutzungsbeschränkung nach <ref-law> zu sistieren, erhöhe das Risiko, dass die Bauherrschaft von vornherein auf eine künftige Sistierung setze. Es würde dem Zweck von <ref-law> und des ZWG offensichtlich zuwiderlaufen, die Erstellung von Wohnungen zu bewilligen, die wahrscheinlich nie als Erstwohnungen genutzt werden könnten (mit Verweis auf <ref-ruling> E. 2.4 in fine S. 54 f.). Würden Erstwohnungen für noch unbekannte Erwerber erstellt, müsse daher glaubhaft gemacht werden, dass im betreffenden Marktsegment eine Nachfrage für Erstwohnungen bestehe (<ref-ruling> E. 2.3 S. 53; Urteil 1C_160/ 2015 vom 3. Mai 2016). Sei die Nachfrage offensichtlich unzureichend, dürfe die Baubewilligung nur erteilt werden, wenn ernsthafte und konkrete Zusicherungen für den Erwerb durch ganzjährige Bewohner vorliegen (<ref-ruling> E. 2.4 S. 54), ansonsten die Baubewilligung verweigert werden müsse.
Das Bundesgericht erachtete die streitigen Wohnungen von Zuschnitt, Ausgestaltung, Lage und Erschliessung her grundsätzlich als für eine Erstwohnnutzung geeignet. Zwar sei mit einem Preis im oberen Segment zu rechnen; dies schliesse jedoch eine Erstwohnnutzung in Gsteig nicht von vornherein aus, sei es doch notorisch, dass im Saanenland auch vermögende Personen ihren Wohnsitz hätten. Das Verwaltungsgericht habe jedoch keinerlei Feststellungen zur Nachfrage nach Erstwohnungen in Gsteig getroffen. Der Hinweis auf die leichte Zunahme der Wohnbevölkerung Gsteigs in den vergangenen Jahren genüge für sich allein nicht, sofern nicht bekannt sei, wie gross das Angebot an Erstwohnungen in der Gemeinde sei. Hierfür müsse ermittelt werden, wie hoch der Wohnungsleerbestand in der Gemeinde sei und wie viele Erstwohnungen in jüngerer Zeit bewilligt bzw. erstellt worden seien. Das Bundesgericht wies die Sache daher an das Verwaltungsgericht zurück, um die notwendigen Auskünfte zu beschaffen; dazu bedürfe es nicht zwingend einer Expertise, sondern die Auskünfte könnten auch bei der Gemeinde oder den kantonalen Behörden eingeholt werden.
An diese Vorgaben war das Verwaltungsgericht gebunden; sie binden auch das Bundesgericht im vorliegenden Verfahren (vgl. oben E. 1.1). Nicht näher einzugehen ist daher auf die Rechtsauffassung der Beschwerdeführer, wonach <ref-law> stets (unabhängig von der Nachfrage nach Erstwohnungen) voraussetze, dass in der Gemeinde wohnhafte Mieter bzw. Käufer sich vertraglich zur ganzjährigen Nutzung der Wohnungen verpflichten.
2.2. Das Verwaltungsgericht stützte sich auf die von der Gemeinde Gsteig am 21. August 2018 erteilten Auskünfte. Danach bestehen in der Gemeinde insgesamt fünf Wohnungen des geplanten Typs ("Erstwohnungen im gehobenen Segment"); alle seien durch Personen mit steuerrechtlichem Wohnsitz in Gsteig bewohnt. Es seien keine weiteren Baubewilligungsverfahren für Wohnungen in diesem Segment hängig und auch keine entsprechenden Baubewilligungen erteilt worden. Demnach seien zurzeit einzig die von der Beschwerdegegnerin geplanten drei Wohnungen als Erstwohnungen im gehobenen Segment auf dem Markt bzw. kämen in nächster Zeit auf den Markt. Die Einwohnerzahl Gsteigs habe zwischen 2007 und 2017 leicht zugenommen, nämlich um rund 0,9 %.
Das Verwaltungsgericht erwog, das umstrittene Vorhaben sehe eine Zweizimmerwohnung (109 m2), eine Fünfzimmerwohnung (163 m2) und eine Vierzimmerwohnung (245 m2) vor. Als Erstwohnungen böten diese Platz für rund acht bis elf Personen. Einen vergleichbaren Anstieg der Einwohnerzahl habe die Gemeinde in den Jahren 2007-2017 mehrmals verzeichnet, weshalb dies nicht bloss theoretisch sei, auch wenn im Jahr 2017 zwölf Personen mehr weg- als zugezogen seien. Unter diesen Umständen sei es nicht von vornherein unrealistisch, die drei geplanten Wohnungen als Erstwohnungen im gehobenen Segment zu nutzen. Es sei somit von einer bestehenden Nachfrage nach den drei Erstwohnungen auszugehen. Daran ändere nichts, dass es der Beschwerdegegnerin bisher nicht gelungen sei, eine Wohnung ab Plan an Ortsansässige zu verkaufen, sei dieser Umstand doch nur eines von mehreren Indizien, um die Nachfrage nach Erstwohnungen zu beurteilen.
3.
Diese Ausführungen sind aus Sicht des Bundesrechts nicht zu beanstanden; die diesbezüglichen Einwände der Beschwerdeführerin erweisen sich als unbegründet:
3.1. Die Beschwerdeführer machen geltend, es würden weitere Luxuswohnungen in Gsteig im Internet als Erstwohnung zum Kauf angeboten, d.h. das Angebot beschränke sich nicht auf die streitigen drei Wohnungen. Sie legen jedoch nicht dar, inwiefern es sich um zulässige Noven i.S.v. <ref-law> handelt. Im Übrigen führen sie selbst aus, dass für diese Projekte noch keine Baugesuche eingereicht wurden. Es ist deshalb ungewiss, ob bzw. wann diese Planungen bewilligt und realisiert werden können. Insofern mussten sie von Gemeinde und Verwaltungsgericht bei der Ermittlung des bestehenden Angebots an Erstwohnungen nicht berücksichtigt werden.
3.2. Die Beschwerdeführer beanstanden weiter, die Gemeinde habe für die Erstwohnnutzung der bestehenden Objekte allein auf den steuerrechtlichen Wohnsitz in Gsteig abgestellt, ohne die Art der Besteuerung zu präzisieren. Es sei unzulässig, auch Personen zu erfassen, die pauschal (nach Aufwand) besteuert würden.
Das Verwaltungsgericht ging dagegen davon aus, es sei vom zivil- bzw. steuerrechtlichen Wohnsitz auszugehen; ob eine Besteuerung nach Aufwand vorliege, sei unerheblich. Dies trifft zu:
Eine Erstwohnung liegt nach <ref-law> vor, wenn eine Wohnung von mindestens einer Person genutzt wird, die gemäss Artikel 3 lit. b des Registerharmonisierungsgesetzes vom 23. Juni 2006 (RHG; SR 431.02) in der Gemeinde, in der die Wohnung liegt, niedergelassen ist. Niederlassungsgemeinde ist die Gemeinde, in der sich eine Person in der Absicht dauernden Verbleibens aufhält, um dort den Mittelpunkt ihres Lebens zu begründen, welcher für Dritte erkennbar sein muss; eine Person wird in derjenigen Gemeinde als niedergelassen betrachtet, in der sie das erforderliche Dokument hinterlegt hat, und kann nur eine Niederlassungsgemeinde haben (vgl. <ref-law>). Dies entspricht dem Hauptwohnsitz einer Person (Botschaft des Bundesrats zum Zweitwohnungsgesetz vom 19. Februar 2014, BBl 2014 2298).
Der steuerrechtliche Wohnsitz verlangt ebenfalls, dass sich eine Person mit der Absicht dauernden Verbleibens aufhält (<ref-law>) und fällt grundsätzlich mit dem zivilrechtlichen Wohnsitzbegriff des ZGB zusammen (vgl. <ref-ruling> E. 2.5.1 S. 237 f.). Insofern kann vom steuerrechtlichen Wohnsitz in der Gemeinde auf die Erstwohnnutzung geschlossen werden. Dies gilt unabhängig vom Umfang der Besteuerung (nach Einkommen oder Aufwand; vgl. dazu <ref-law>).
3.3. Die Beschwerdeführer erachten es als willkürlich, eine Nachfrage nach Erstwohnungen aufgrund der überaus leichten Bevölkerungszunahme von 0.9 % über einen Zeitraum von 10 Jahren zu bejahen. Massgeblich sei vielmehr, dass die Bevölkerung seit Annahme der Zweitwohnungsinitiative um 16 Personen zurückgegangen sei.
Zwar ist das Bevölkerungswachstum gering; auch das Angebot an Erstwohnungen im gehobenen Segment (nur drei Wohnungen für insgesamt 8-11 Personen) ist jedoch klein. Es trifft zu, dass im Jahr 2017 zwölf Personen mehr weg- als zugezogen sind; entgegen der Auffassung der Beschwerdeführer ist jedoch kein klarer Abwärtstrend erkennbar, gab es doch in den Jahren davor (2012, 2013 und 2016) mehrfach einen positiven Saldo. Unter diesen Umständen erscheint die Einschätzung des Verwaltungsgerichts nicht als offensichtlich unrichtig.
3.4. Die Beschwerdeführer rügen weiter, die von der Beschwerdegegnerin angegebenen Verkaufspreise seien unrealistisch tief. Dies mag zutreffen, erscheint jedoch nicht entscheiderheblich: Das Bundesgericht hat bereits im Urteil 1C_592/2017 erwogen, dass mit mit einem Preis im oberen Segment zu rechnen sei, was jedoch eine Erstwohnnutzung in Gsteig nicht von vornherein ausschliesse. Die Rückweisung an das Verwaltungsgericht erfolgte vielmehr, um den Wohnungsleerbestand und die Anzahl gebauter bzw. bewilligter Wohnungen im gehobenen Segment abzuklären. Nachdem kein Leerbestand vorliegt, die von der Beschwerdegegnerin geplanten drei Wohnungen das einzige (aktuelle) Angebot in diesem Sektor darstellen und ein Bevölkerungszuwachs in Höhe von 8-11 Personen möglich erscheint, durfte das Verwaltungsgericht eine Umgehung des Zweitwohnungsverbots verneinen.
3.5. Das Verwaltungsgericht war auch nicht gehalten, der Gemeinde Ergänzungsfragen zu stellen oder die von den Beschwerdeführern beantragten Zeugen einzuvernehmen. Es durfte die entsprechenden Beweisanträge der Beschwerdeführer ohne Verletzung des rechtlichen Gehörs abweisen, weil keine zusätzlichen Ermittlungen erforderlich waren (insbesondere zur Steuerart) und von der Einvernahme der schweizweit tätigen Immobilienexperten keine weiteren Aufschlüsse zur konkreten Nachfrage in Gsteig zu erwarten waren. Bereits im Urteil 1C_592/2017 vom 15. Juni 2018 (E. 5.7) hatte das Bundesgericht festgehalten, dass es nicht zwingend der von den Beschwerdeführern beantragten Expertise bedürfe, sondern es genüge, wenn Auskünfte bei der Gemeinde oder den kantonalen Behörden eingeholt würden.
Es besteht daher auch kein Grund, diese Beweise im bundesgerichtlichen Verfahren abzunehmen, wie subsidiär von den Beschwerdeführern beantragt.
4.
4.1. Die Beschwerdeführer rügen weiter, das Verwaltungsgericht habe verschiedene von ihnen gestellte Anträge im Zusammenhang mit dem Beginn der Bauarbeiten auf Parzelle 880 nicht behandelt. Dies trifft indes nicht zu:
Mit Eingabe vom 4. Oktober 2018 teilten die Beschwerdeführer mit, dass die Bauherrschaft mit dem Bau begonnen habe; da die hängige Beschwerde aufschiebende Wirkung habe, habe sie sich offensichtlich für die Realisierung des ersten Projekts entschieden. Die Beschwerdeführer beantragten daher, das Beschwerdeverfahren gegen das zweite Bauprojekt sei als gegenstandslos abzuschreiben. Die Beschwerdegegnerin antwortete, sie habe mit dem Baugrubenaushub einzig begonnen, damit die Baubewilligung 2012/2015 nicht verfalle, habe sich aber noch nicht definitiv für das erste Projekt entschieden. Die Baugrube sei nicht projektspezifisch und könne auch für das neue Projekt verwendet werden, falls die Baubewilligung bestätigt werde.
Daraufhin beantragten die Beschwerdeführer mit Eingabe vom 19. November 2018, der Beschwerdegegnerin sei zu befehlen, innert einem Monat die Baugrube zu beseitigen. Der Instruktionsrichter qualifizierte diesen Antrag als baupolizeiliche Anzeige und überwies sie zuständigkeitshalber der Gemeinde (Verfügung vom 21. November 2018); gleichzeitig setzte er den Beschwerdeführern Frist, um zu erklären, ob sie an ihrem Antrag auf Abschreibung des Beschwerdeverfahrens festhielten.
Die Beschwerdeführer beantragten daraufhin die Sistierung des Beschwerdeverfahrens bis zum Ergebnis des baupolizeilichen Verfahrens der Gemeinde (Eingabe vom 5. Dezember 2018). Der Instruktionsrichter interpretierte diesen Antrag dahin, dass sie das Beschwerdeverfahren - wenn auch mit einem vorläufigen Unterbruch - fortführen wollten, d.h. der Antrag vom 4. Oktober 2018 auf Abschreibung des Verfahrens gegenstandslos geworden sei. Er stellte dies mit Verfügung vom 21. Dezember 2018fest und wies den Sistierungsantrag ab.
Damit wurden alle Anträge behandelt, durch Überweisung, Abweisung oder indem sie als gegenstandslos erklärt wurden.
4.2. Die Beschwerdeführer rügen die Überweisung ihres Antrags auf Beseitigung der Baugrube als Baupolizeianzeige an die Gemeinde als willkürlich, begründen dies aber nicht genügend, weshalb darauf nicht einzutreten ist.
4.3. Wie bereits dargelegt (oben E. 1.2), war Gegenstand des Verfahrens nur die zweite Baubewilligung vom 25. Juli 2016. Das Verwaltungsgericht durfte daher auf Anträge zum Fortbestand der ersten (2012 erteilten) Baubewilligung nicht eintreten und den Antrag auf Beizug der Akten des ersten Projekts abweisen, ohne das rechtliche Gehör der Beschwerdeführer zu verletzen. Diese Unterlagen sind auch vor Bundesgericht nicht beizuziehen.
5.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin für die Kosten des bundesgerichtlichen Verfahrens mit Fr. 4'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Einwohnergemeinde Gsteig, dem Regierungsstatthalteramt Obersimmental-Saanen, der Bau-, Verkehrs- und Energiedirektion und dem Verwaltungsgericht des Kantons Bern, Verwaltungsrechtliche Abteilung, sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 17. April 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Gerber