Citation: 2C_493/2019 E. A

A.a. Die zuständige niederländische Steuerbehörde (Belastingdienst [BD]) richtete am 5. Dezember 2017 gestützt auf Art. 26 des Abkommens vom 26. Februar 2010 zwischen der Schweizerischen Eidgenossenschaft und dem Königreich der Niederlande zur Vermeidung der Doppelbesteuerung auf dem Gebiet der Steuern vom Einkommen (DBA CH-NL; SR 0.672.963.61) ein Amtshilfegesuch an die Eidgenössische Steuerverwaltung (ESTV), welches die in den Niederlanden steuerpflichtigen A.A.________ und B.A.________ betrifft. Das Amtshilfegesuch bezieht sich auf die Einkommenssteuer der letzteren für den Zeitraum 1. März 2010 bis 31. Dezember 2016. Der BD ersucht bezüglich der Konten mit den Nr. xxx, yyy und zzz bei der Bank B.________, U.________, um Angabe bzw. Übermittlung der Kontoinhaber, Berechtigten und Bevollmächtigten, Kontaktadressen, Kontoeröffnungsunterlagen, Anfangs- und Jahresendsaldi, Transaktionen, anderer mit diesen Konten verbundenen Konten oder Bankprodukte der Bank B.________ (und falls solche vorhanden sind, die Kontoauszüge und/oder Saldi) und allfälliger Kontoschliessungsunterlagen. Im Wesentlichen dieselben Informationen werden zudem verlangt, falls die genannten Steuerpflichtigen in der Vergangenheit oder gegenwärtig Inhaber, Berechtigte oder Bevollmächtigte eines anderen Bankkontos, einer Kreditkarte oder eines sonstigen Bankprodukts der Bank B.________ waren oder sind. A.b. Im genannten Amtshilfegesuch hielt der Vertreter des BD fest: "I confirm that all the usual possibilities of investigation are exhausted." Im Rahmen des Verfahrens vor der ESTV machten die genannten Steuerpflichtigen mit Stellungnahme vom 13. Juni 2018 geltend, die mittels Amtshilfegesuch verlangten Informationen seien bereits durch eine Informationsverfügung gemäss innerstaatlichem Steuerverfahren angefordert worden, wobei sie gegen diese Einsprache erhoben hätten, welche noch hängig sei. Aufgrund Diskrepanzen zwischen dem französischen und dem niederländischen Wortlaut von Ziff. XVI lit. a des Protokolls zum DBA CH-NL sei dessen englischer Wortlaut massgebend, welcher vor Stellung eines Amtshilfegesuchs die Ausschöpfung "aller verfügbaren innerstaatlichen Verfahrensmittel" verlange ("once [...] has pursued all means available to obtain information available under the internal tax procedure"). Das Amtshilfegesuch verletze deshalb die genannte Protokollbestimmung. Mit E-Mail vom 17. Oktober 2018 fragte die ESTV beim BD nach, ob auch ohne Vorliegen einer in Rechtskraft erwachsenen Informationsverfügung "alle (üblichen) Mittel im Sinne von Ziffer XVI Buchstabe a" des genannten Protokolls ausgeschöpft seien und bat um eine Erläuterung des niederländischen Instituts der Informationsverfügung. Mit E-Mail vom 22. Oktober 2018 hielt der BD fest: "In Antwort auf Ihre Frage bestätige ich, dass auch ohne Eröffnung einer Informationsverfügung alle (üblichen) Mittel ausgeschöpft sind." Mit zwei weiteren Eingaben an die ESTV vom 9. und 12. November 2018 nahmen die genannten Steuerpflichtigen unter anderem auf diesen E-Mail-Verkehr Bezug und hielten an ihrer Position, wonach nicht alle verfügbaren innerstaatlichen Mittel ausgeschöpft seien, fest.