Sachverhalt:
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.
B.
Mit Schlussverfügung vom 6. Dezember 2018 ordnete die ESTV die Übermittlung der ersuchten Informationen an den BD an. Die dagegen von A.A._ und B.A._ erhobene Beschwerde vom 4. Januar 2019 wurde vom Bundesverwaltungsgericht mit Urteil vom 13. Mai 2019 abgewiesen.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 24. Mai 2019 beantragen A.A._ (Beschwerdeführerin) und B.A._ (Beschwerdeführer) die Aufhebung des vorinstanzlichen Urteils und der Schlussverfügung der ESTV vom 6. Dezember 2018. Dem BD sei in Sachen der Beschwerdeführer keine Amtshilfe zu leisten. Eventualiter seien das vorinstanzliche Urteil und die Schlussverfügung der ESTV vom 6. Dezember 2018 aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem sei der Beschwerde die aufschiebende Wirkung zu erteilen.
Während die Vorinstanz in ihrer Vernehmlassung auf das vorinstanzliche Urteil verweist, beantragt die ESTV mit Eingabe vom 28. Juni 2019, auf die Beschwerde nicht einzutreten und eventualiter diese abzuweisen. Die Beschwerdeführer haben mit Eingabe vom 17. Juli 2019 repliziert.

Erwägungen:
1.
1.1. Das angefochtene Urteil wurde vom Bundesverwaltungsgericht gefällt und unterliegt als Endentscheid in einer Angelegenheit des öffentlichen Rechts grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a, Art. 86 Abs. 1 lit. a, Art. 90 BGG).
1.2. Gegen Entscheide auf dem Gebiet der internationalen Amtshilfe in Steuersachen ist die Beschwerde zulässig (<ref-law>), wenn sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (<ref-law>) oder es sich aus anderen Gründen um einen besonders bedeutenden Fall im Sinne von Art. 84a i.V.m. <ref-law> handelt. In der Beschwerde ist detailliert aufzuzeigen, dass und weshalb die jeweilige Sachurteilsvoraussetzung erfüllt ist (<ref-law>), es sei denn, dies treffe ganz offensichtlich zu (<ref-ruling> E. 1.3 S. 410; <ref-ruling> E. 4 S. 342).
1.3. Sowohl <ref-law> als auch <ref-law> bezwecken die wirksame Begrenzung des Zugangs zum Bundesgericht im Bereich der internationalen Amtshilfe in Steuerangelegenheiten. Das Vorliegen einer Rechtsfrage von grundsätzlicher Bedeutung ist regelmässig zu bejahen, wenn der Entscheid für die Praxis wegleitend sein kann, namentlich wenn von unteren Instanzen viele gleichartige Fälle zu beurteilen sein werden. Eine Rechtsfrage von grundsätzlicher Bedeutung ist unter Umständen auch anzunehmen, wenn es sich um eine erstmals zu beurteilende Frage handelt, die einer Klärung durch das Bundesgericht bedarf. Es muss sich allerdings um eine Rechtsfrage handeln, die von ihrem Gewicht her nach einer höchstrichterlichen Klärung ruft. Aber auch eine vom Bundesgericht bereits entschiedene Rechtsfrage kann von grundsätzlicher Bedeutung sein, wenn sich die erneute Überprüfung aufdrängt. Dies kann zutreffen, wenn die Rechtsprechung in der massgebenden Lehre auf erhebliche Kritik gestossen ist. Rechtsfragen von grundsätzlicher Bedeutung können sich ebenfalls nach dem Erlass neuer materiell- oder verfahrensrechtlicher Normen stellen. Das Gleiche gilt, wenn sich aufgrund der internationalen Entwicklungen Fragen von grundsätzlicher Bedeutung stellen (<ref-ruling> E. 1.3 S. 410; <ref-ruling> E. 4 S. 342 f. mit weiteren Hinweisen).
Ein besonders bedeutender Fall im Sinne von <ref-law> ist nur mit Zurückhaltung anzunehmen. Diesbezüglich steht dem Bundesgericht ein weiter Ermessensspielraum zu. Gemäss <ref-law> liegt ein besonders bedeutender Fall insbesondere vor, wenn Gründe für die Annahme bestehen, dass elementare Verfahrensgrundsätze verletzt worden sind oder das Verfahren im Ausland schwere Mängel aufweist. Das Gesetz enthält nach dem ausdrücklichen Wortlaut von <ref-law> eine nicht abschliessende Aufzählung von möglichen besonders bedeutenden Fällen (BGE <ref-ruling> E. 4 S. 342 f.).
Die zu beurteilenden Rechtsfragen müssen schliesslich entscheidrelevant sein. Das Bundesgericht prüft nicht Fragen rein theoretischer Natur, die keine konkrete Auswirkung für die Parteien haben (<ref-ruling> E. 3 S. 173; Urteile 2C_275/2017 vom 20. März 2017 E. 2.7; 2C_20/2017 vom 25. Januar 2017 E. 2.1).
1.4. Die Beschwerdeführer machen geltend, die vorgängige Ausschöpfung der im innerstaatlichen Steuerverfahren vorgesehenen Mittel zur Informationsbeschaffung sei eine Voraussetzung für die Informationsübermittlung im Rahmen des DBA CH-NL. Die Sprachfassungen der diesbezüglich entscheidenden Ziff. XVI lit. a des Protokolls zum DBA CH-NL würden voneinander abweichen. Die französische Fassung laute: "Il est entendu que l'Etat requérant formule ses demandes de renseignements uniquement après avoir utilisé tous les moyens de procédure habituels prévus par son droit interne aux fins d'obtenir ces renseignements."
Auf Niederländisch laute dieselbe Bestimmung: "Het is wel te verstaan dat uitsluitend om uitwisseling van inlichtingen zal worden verzocht nadat de verzoekende Verdragsluitende Staat alle beschikbare middelen heeft aangewend om inlichtingen te verkrijgen die beschikbaar zijn volgens de nationale belastingprocedure."
Der französische Wortlaut spreche von den "üblichen", der niederländische dagegen von "allen" Mitteln. Das Protokoll zum DBA CH-NL sehe diesbezüglich vor, dass der Wortlaut in französischer, niederländischer und englischer Sprache gleicherweise verbindlich sei, wobei im Falle unterschiedlicher Auslegung der englische Wortlaut massgebend sei. Letzterer laute: "it is understood that an exchange of information will only be requested once the requesting Contracting State has pursued all means available to obtain information available under the internal taxation procedure." Demzufolge müsse die Niederlande zwingend innerstaatlich zuerst alle verfügbaren Mittel angewendet haben, bevor sie ein Amtshilfegesuch stellen könne.
Die Beschwerdeführer sind im Wesentlichen der Auffassung, die Vorinstanz habe klares Recht verletzt, indem sie die Regelung "all means available" ignoriere und ohne Weiteres auf den Begriff der "üblichen Mittel" abgestellt habe. Bereits aufgrund des Wortlautes müssten zuerst "alle verfügbaren Mittel" angewendet werden. Demzufolge müsse das Verfahren bezüglich Informationsverfügung zuerst abgeschlossen werden. Da dieses noch hängig sei, seien die verfügbaren, innerstaatlichen Mittel noch nicht ausgeschöpft. Die Vorinstanz habe das Subsidiaritätsprinzip, so wie es im DBA CH-NL geregelt sei, verletzt. In der Frage, ob gemäss Ziff. XVI lit. a des Protokolls zum DBA CH-NL der ersuchende Staat innerstaatlich zuerst "alle verfügbaren Mittel" oder bloss "alle üblichen Mittel" ausgeschöpft haben muss, bevor er ein Amtshilfegesuch stellen darf, erblicken die Beschwerdeführer eine Rechtsfrage von grundsätzlicher Bedeutung.
1.5. Gemäss dem letzten Absatz des Protokolls zum DBA CH-NL bestehen drei verbindliche Sprachfassungen desselben in französischer, niederländischer und englischer Sprache. Eine Übersetzung des entsprechenden niederländischen Wortlautes "alle beschikbare middelen" in die französische Sprache ergibt "tous les moyens possibles" und alternativ "tous les moyens disponibles", in die englische Sprache "all means available" (<https://www.deepl.com>, besucht am 13. November 2019). Eine Übersetzung des entsprechenden französischen Wortlautes "tous les moyens [...] habituels" in die niederländische Sprache ergibt "alle gebruikelijke middelen", in die englische Sprache "all the usual means" (<https://www.deepl.com>, besucht am 13. November 2019). Das entsprechende englische Protokoll enthält den Wortlaut "all means available". Während der niederländische und der englische Wortlaut übereinstimmen, besteht zwischen dem französischen auf der einen und dem niederländischen bzw. englischen Wortlaut auf der anderen Seite eine Diskrepanz. Der niederländische und der englische Protokollwortlaut entsprechen in deutscher Sprache der Wendung "alle verfügbaren Mittel" (<https://www.deepl.com>, besucht am 13. November 2019), während der französische Protokollwortlaut in deutscher Sprache der Wendung "alle üblichen Mittel" oder "alle gängigen Mittel" entspricht.
Gemäss dem letzten Absatz des Protokolls zum DBA CH-NL (in seiner französischen, niederländischen und englischen Sprachfassung) ist bei "unterschiedlicher Auslegung" der französischen und niederländischen Sprachfassungen der englische Wortlaut massgebend. Nach dem hier einschlägigen Wiener Übereinkommen über das Recht der Verträge vom 23. Mai 1969 (VRK; SR 0.111) ist Ausgangspunkt der Auslegung der Wortlaut (<ref-ruling> E. 5.2.2 S. 148; Urteil 2C_306/2017 vom 3. Juli 2019 [zur Publikation vorgesehen] E. 4.4.2). Dieser ist unterschiedlich, weshalb ein unterschiedliches Auslegungsergebnis als möglich erscheint. Die Frage, welche Bedeutung dem betroffenen Protokollwortlaut gemäss Auslegung zukommt und ob in diesem Zusammenhang eine Verletzung des Subsidiaritätsprinzips vorliegt, wurde vom Bundesgericht bislang nicht entschieden. Von ihrem Gewicht her ruft diese Fragestellung nach einer höchstrichterlichen Klärung. Demzufolge handelt es sich um eine Rechtsfrage von grundsätzlicher Bedeutung, weshalb auf die form- und fristgerecht eingereichte Beschwerde einzutreten ist.
1.6. Gegenstand des bundesgerichtlichen Verfahrens bildet ausschliesslich das vorinstanzliche Urteil, welches aufgrund des Devolutiveffekts insbesondere die diesem vorangegangene Schlussverfügung der ESTV vom 6. Dezember 2018 ersetzt. Die dem vorinstanzlichen Urteil zugrunde liegenden Verfügungen und Entscheide gelten durch die Beschwerde vor Bundesgericht als mit angefochten. Sie können im bundesgerichtlichen Verfahren demzufolge nicht eigenständig angefochten werden. Auf den Antrag, die genannte Schlussverfügung der ESTV aufzuheben, ist deshalb nicht einzutreten (<ref-ruling> E. 2.5 S. 415; <ref-ruling> E. 1.2 S. 543).
1.7. Der Beschwerde in öffentlich-rechtlichen Angelegenheiten kommt in Verfahren auf dem Gebiet der internationalen Amtshilfe in Steuersachen von Gesetzes wegen aufschiebende Wirkung zu (<ref-law>). Der vorliegende Antrag, der Beschwerde aufschiebende Wirkung zu erteilen, erweist sich damit als gegenstandslos, weshalb auf diesen nicht einzutreten ist.
2.
2.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>).
2.2. Das vorliegende Amtshilfeverfahren richtet sich nach dem DBA CH-NL sowie nach dem Bundesgesetz vom 28. September 2012 über die internationale Amtshilfe in Steuersachen (StAhiG; SR 651.1).
3.
3.1. Die Beschwerdeführer rügen eine Verletzung des Anspruchs auf rechtliches Gehör (<ref-law>). Sie machen geltend, die Vorinstanz habe ihre erheblichen Vorbringen bezüglich unter anderem des Subsidiaritätsprinzips überhaupt nicht berücksichtigt und ihr Vorgehen in keiner Weise begründet. Trotz detaillierter Ausführungen, Argumente und Beilage zahlreicher Unterlagen, wonach zuerst "alle verfügbaren Mittel" ausgeschöpft werden müssten, sei die Vorinstanz darauf nicht eingegangen und habe ohne Begründung auf den Begriff "alle üblichen Mittel" abgestellt. Die Beschwerdeführer rügen in diesem Zusammenhang auch die Verletzung der Begründungspflicht als Teilgehalt des rechtlichen Gehörs und machen ebenfalls eine materielle und formelle Rechtsverweigerung geltend.
3.2. Aus dem Anspruch auf rechtliches Gehör nach <ref-law> fliesst die Pflicht der Behörden, die Vorbringen des von einem Entscheid in seiner Rechtsstellung Betroffenen tatsächlich zu hören, zu prüfen und in der Entscheidfindung zu berücksichtigen (<ref-ruling> E. 5.2 S. 236; Urteile 2C_432/2016 vom 26. Januar 2018 E. 3.2.1; 2C_147/2017 vom 23. Januar 2018 E. 2.6.2). Zudem ergibt sich aus dieser Verfahrensgarantie die Begründungspflicht. Letztere verlangt allerdings nicht, dass sich das Gericht mit sämtlichen vorgebrachten Sachverhaltselementen, Beweismitteln und Rügen auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann es sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinne müssen wenigstens kurz die Überlegungen genannt werden, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt (<ref-ruling> E. 5.2 S. 70 f.; <ref-ruling> E. 4.1 S. 88 f.; Urteil 6B_651/2018 vom 17. Oktober 2018 E. 8.3.1). Die Begründungspflicht ist nur dann verletzt, wenn das Gericht auf die für den Ausgang des Verfahrens wesentlichen Vorbringen selbst implizit nicht eingeht (<ref-ruling> E. 5.2 S. 248 f.).
3.3. Das vorinstanzliche Urteil nimmt auf die unterschiedlichen Sprachfassungen des relevanten Protokolltextes - wenn auch nur sehr kurz - Bezug und hält zudem fest, dass nach bundesverwaltungsgerichtlicher Rechtsprechung nicht das Ausschöpfen sämtlicher möglicher Mittel verlangt werde (E. 5 und 5.1 des vorinstanzlichen Urteils). Anschliessend und abgesehen davon stellt die Vorinstanz ausschliesslich auf den Begriff der "üblichen Mittel" ab. Auch wenn sie sich demnach kaum mit der bereits vor der Vorinstanz vorgetragenen Auslegung der unterschiedlichen Sprachfassungen und den entsprechenden Argumenten hinsichtlich des Subsidiaritätsprinzips auseinandersetzt, geht damit keine Verletzung des Anspruchs auf rechtliches Gehör respektive der Begründungspflicht einher. Jedenfalls ergibt sich aus der vorinstanzlichen Urteilsbegründung, dass die Vorinstanz die entsprechenden Vorbringen gehört hat. Das Unterlassen einer detaillierten Auseinandersetzungen mit den Vorbringen der Beschwerdeführer führt zudem nicht zu einer Verletzung der Begründungspflicht, denn die Beschwerdeführer waren in der Lage, das vorinstanzliche Urteil sachgerecht anzufechten, wie sich auch aus der Beschwerdeschrift ergibt. Das vorinstanzliche Urteil erweist sich somit bezüglich Gewährung des rechtlichen Gehörs als bundesrechtskonform.
4.
Im Weiteren rügen die Beschwerdeführer eine formelle Rechtsverweigerung, welche sie darin erblicken, dass die Vorinstanz keine Auslegung der betroffenen Protokollbestimmung vorgenommen habe.
4.1. Das Verbot der formellen Rechtsverweigerung wird rechtsprechungsgemäss aus <ref-law> abgeleitet, wonach jede Person in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf gleiche und gerechte Behandlung sowie auf Beurteilung innert angemessener Frist hat. Rechtsprechungsgemäss liegt eine formelle Rechtsverweigerung vor, wenn ein Gericht oder eine Behörde auf eine Eingabe fälschlicherweise nicht eintritt, eine Eingabe nicht an die Hand nimmt und behandelt (<ref-ruling> E. 3 S. 192 f.; Urteil 1D_8/2018 vom 3. April 2019 E. 4.1), den Entscheid nicht innert angemessener Frist trifft oder wenn sie ihre Kognitionsbefugnis in unzulässiger Weise beschränkt (<ref-ruling> E. 2.a S. 71; Urteil 1P.609/1993 vom 26. April 1994 E. 2 mit Hinweisen). Zudem liegt eine formelle Rechtsverweigerung auch dann vor, wenn die Prüfung eines Rechtsbegehrens unterlassen wird, obwohl dazu eine Verpflichtung besteht (Urteil 4A_116/2015, 4A_118/2015 vom 9. November 2015 E. 7.1, nicht publ. in: <ref-ruling>).
4.2. Die Vorinstanz ist auf die an sie gerichtete Beschwerde eingetreten, was zum vorliegend angefochtenen Urteil geführt hat. Im Umstand, dass die Vorinstanz die aufgeworfenen Rechtsfragen anders als von den Beschwerdeführern gefordert behandelt und insbesondere keine Auslegung der betroffenen Protokollbestimmung vorgenommen hat, weil sie dies nicht als rechtserheblich erachtete, liegt rechtsprechungsgemäss keine formelle Rechtsverweigerung. Das vorinstanzliche Urteil erweist sich diesbezüglich als bundesrechtskonform.
4.3. Zudem machen die Beschwerdeführer geltend, die Vorinstanz habe ihr Vorgehen, nämlich die Unterlassung der Auslegung, nicht einmal begründet und damit willkürlich und falsch gehandelt, was eine materielle Rechtsverweigerung darstelle. Dem kann von Vornherein nicht gefolgt werden, denn wie sich aus E. 3.3 oben ergibt, hat die Vorinstanz für ihr Vorgehen eine wenn auch minimale Begründung vorgelegt.
5.
5.1. Im Folgenden ist die aufgeworfene Rechtsfrage von grundsätzlicher Bedeutung zu klären. Da der französische und der niederländische Text des betroffenen Protokolls unterschiedlich sind, ist zunächst der niederländische Wortlaut, nämlich "alle beschikbare middelen", welcher übersetzt in die deutsche Sprache "alle verfügbaren Mittel" lautet, nach der VRK auszulegen.
5.2. Die Beschwerdeführer sind der Ansicht, bereits der Wortlaut des niederländischen und englischen Protokolls sei klar genug ("alle verfügbaren Mittel") und eine weitere Auslegung deshalb weder nötig noch zulässig. Sollte eine Auslegung dennoch nötig sein, führe sie zum selben Ergebnis. Sie verweisen diesbezüglich auf niederländische Literatur, wonach das Protokoll zum DBA CH-NL bezüglich Subsidiaritätsprinzip strenger sei als Art. 5 Abs. 5 lit. g des OECD-Modells zum Informationsaustausch (TIEA-Modell). Zudem zitieren sie Aussagen eines Vertreters des BD und eines niederländischen Staatssekretärs für Finanzen, wonach in den Niederlanden zuerst "alles Mögliche" getan werden müsse, um die Informationen zu erhalten respektive dass sich der Steuerpflichtige auf das sog. "Dezentjé-Gesetz" berufen könne, gemäss welchem zuerst das innerstaatliche Informationsverfügungsverfahren durchlaufen werden müsse. Letzteres sei sogar als übliches Verfahren zu betrachten und wenn nicht einmal dieses ausgeschöpft sei, könne erst Recht keine Rede davon sein, dass "alle Mittel" ausgeschöpft seien. Entgegen der Vorinstanz sei es zudem falsch und aktenwidrig, dass der Steuerpflichtige nach Erlass der Informationsverfügung die Steuerfaktoren nicht mehr spontan deklarieren könne. Letzteres sei vielmehr innert einer bestimmten Frist auch nach einer rechtskräftigen Informationsverfügung noch möglich. Im Weiteren verletze das vorinstanzliche Urteil auch das Vertrauensprinzip, wenn es letzteres dermassen streng anwende, dass eine simple Erklärung des BD, wonach die üblichen Mittel ausgeschöpft seien, genüge. Das Subsidiaritätsprinzip verliere zudem komplett seine Bedeutung, wenn ein Staat wie vorliegend praktisch direkt ein Amtshilfeverfahren einleiten könne, ohne die Rechte der Steuerpflichtigen durch Ausschöpfung des innerstaatlichen Steuerverfahrens zu wahren.
5.3. Nach Art. 31 Abs. 1 VRK haben die Vertragsstaaten eine zwischenstaatliche Übereinkunft nach Treu und Glauben in Übereinstimmung mit der gewöhnlichen, ihren Bestimmungen in ihrem Zusammenhang zukommenden Bedeutung und im Lichte ihres Ziels und Zwecks auszulegen. Neben dem Zusammenhang sind gemäss Art. 31 Abs. 3 VRK in gleicher Weise jede spätere Übereinkunft zwischen den Vertragsparteien über die Auslegung des Vertrags oder die Anwendung seiner Bestimmungen (lit. a), jede spätere Übung bei der Anwendung des Vertrags, aus der die Übereinstimmung der Vertragsparteien über seine Auslegung hervorgeht (lit. b), sowie jeder in den Beziehungen zwischen den Vertragsparteien anwendbare einschlägige Völkerrechtssatz (lit. c) zu berücksichtigen. Die vorbereitenden Arbeiten und die Umstände des Vertragsabschlusses sind nach Art. 32 VRK ergänzende Auslegungsmittel und können herangezogen werden, um die nach Art. 31 VRK ermittelte Bedeutung zu bestätigen oder die Bedeutung zu bestimmen, wenn die Auslegung nach Art. 31 VRK die Bedeutung mehrdeutig oder dunkel lässt (Art. 32 lit. a VRK) oder zu einem offensichtlich sinnwidrigen oder unvernünftigen Ergebnis führt (Art. 32 lit. b VRK; Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.1; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; 2C_306/2017 vom 3. Juli 2019 E. 4.4.2; je mit Hinweisen und zur Publikation vorgesehen; <ref-ruling> E. 8.2 S. 139 mit Hinweisen; <ref-ruling> E. 5.2 mit Hinweisen).
5.4. Art. 31 Abs. 1 VRK bestimmt eine Reihenfolge der Berücksichtigung der verschiedenen Auslegungselemente, ohne dabei eine feste Rangordnung unter ihnen festzulegen. Den Ausgangspunkt der Auslegung eines völkerrechtlichen Vertrags bildet jedoch die gewöhnliche Bedeutung seines Wortlautes bzw. seiner Bestimmungen (Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.2; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; je mit Hinweisen und zur Publikation vorgesehen; <ref-ruling> E. 8.2.1 S. 130; <ref-ruling> E. 6.3.1 S. 208; <ref-ruling> E. 5.2.2 S. 148). Diese gewöhnliche Bedeutung ist nach Treu und Glauben und unter Berücksichtigung ihres Zusammenhangs und des Ziels und Zwecks des Vertrags zu bestimmen (Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.2; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; je mit Hinweisen und zur Publikation vorgesehen; <ref-ruling> E. 8.2.1 S. 139; <ref-ruling> E. 6.3.1 S. 208; <ref-ruling> E. 5.2.2 S. 148). Ziel und Zweck des Vertrags ist dabei, was mit dem Vertrag erreicht werden sollte. Zusammen mit der Auslegung nach Treu und Glauben stellt die teleologische Auslegung den "effet utile" des Vertrags sicher (Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.2; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; je mit Hinweisen; <ref-ruling> E. 8.2.1 S. 139; <ref-ruling> E. 5.2.2 S. 148; <ref-ruling> E. 2.1.3 S. 167; <ref-ruling> E. 3.5.1 S. 503). Der auszulegenden Bestimmung eines Doppelbesteuerungsabkommens ist unter mehreren möglichen Interpretationen demnach derjenige Sinn beizumessen, welcher ihre effektive Anwendung gewährleistet und nicht zu einem Ergebnis führt, das dem Ziel und Zweck der eingegangenen Verpflichtungen widerspricht (Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.2; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; je mit Hinweisen und zur Publikation vorgesehen; <ref-ruling> E. 5.2.2 S. 149; <ref-ruling> E. 2.1.3 S. 167). Ausserdem sind die Vertragsstaaten nach Treu und Glauben gehalten, jedes Verhalten und jede Auslegung zu unterlassen, mittels welcher sie ihre vertraglichen Pflichten umgehen oder den Vertrag seines Ziels und Zwecks entleeren würden (Urteile 2C_209/2017 vom 16. Dezember 2019 E. 3.1.2; 2C_653/2018 vom 26. Juli 2019 E. 5.3.2; je mit Hinweisen; <ref-ruling> E. 8.2.1 S. 139; <ref-ruling> E. 6.3.1 S. 208; <ref-ruling> E. 2.1.3 S. 167).
5.5.
5.5.1. Die gewöhnliche Bedeutung des Wortlautes "alle verfügbaren" Mittel weist über "alle üblichen" Mittel hinaus. Beide Wortlaute sind indessen auslegungsbedürftig. Bei er Auslegung sind insbesondere Ziel und Zweck der internationalen Amtshilfe in Steuersachen zu berücksichtigen. In deren Rahmen sollen sich die Vertragsstaaten relativ rasch gegenseitig mit Informationen zwecks Steuerveranlagung unterstützen (vgl. <ref-law>), sofern das Amtshilfegesuch bestimmten formellen und inhaltlichen Anforderungen genügt. Eine dieser Anforderungen ist die Erfüllung des Subsidiaritätsprinzips. Das Subsidiaritätsprinzip soll vermeiden, dass auf den ersuchten Staat die Last überwälzt wird, Auskünfte zu erteilen, welche dem ersuchenden Staat nach innerstaatlichem Recht zugänglich sind (<ref-ruling> E. 3.3.1 S. 211). Hier stellt sich die Frage, wie weit der ersuchende Staat diesbezüglich gehen muss und inwiefern der ersuchte Staat überprüfen kann und soll, ob dem Subsidiaritätsprinzip genüge getan wurde. Eng verbunden mit dem Subsidiaritätsprinzip ist das Vertrauensprinzip (<ref-ruling> E. 3.3.2 S. 211; Urteil 2C_904/2015 vom 8. Dezember 2016 E. 7.2). Was bezüglich der Behauptung des ersuchenden Staates, die Informationen seien (für die Steuerveranlagung) voraussichtlich erheblich, gilt, muss auch in Bezug auf die Behauptung, dass Subsidiaritätsprinzip sei eingehalten, gelten: Grundsätzlich ist es dem ersuchten Staat weder möglich noch ist es dessen Aufgabe, zu verifizieren, ob der ersuchende Staat gemäss seinem (internen) Steuerverfahrensrecht bereits die nötigen Schritte unternommen hat, um der Subsidiarität gerecht zu werden (vgl. Urteil 2C_241/2016 vom 7. April 2017 E. 5.4). Bei ernsthaften Zweifeln kann der ersuchte Staat vom ersuchenden Staat eine Klärung verlangen (<ref-ruling> E. 3.3.2 S. 211; <ref-ruling> E. 8.7.1 S. 221 f.; Urteil 2C_904/2015 vom 8. Dezember 2016 E. 7.2).
Es kann deshalb im zwischenstaatlichen Verhältnis nicht relevant sein, ob der Steuerpflichtige im ersuchenden Staat nach Einreichung der Steuererklärung erst aufgefordert wurde, gewisse Informationen nachzuliefern oder ob bereits ein entsprechendes Informationsbeschaffungsverfahren rechtskräftig abgeschlossen wurde. Wenn der ersuchte Staat darauf beharren würde, dass im ersuchenden Staat zuerst Rechtsmittelverfahren bezüglich Informationsbeschaffung rechtskräftig abgeschlossen sind, würde dies neben der möglichen Beeinträchtigung des völkerrechtlichen Vertrauensprinzips zu einer erheblichen Zeitverzögerung führen, was mit der internationalen Verpflichtung eines speditiven Informationsaustausches nicht vereinbar ist (vgl. Urteil 2C_726/2018 vom 14. Oktober 2019 E. 3.5). Demzufolge sind auch die Verweise der Beschwerdeführer auf Literaturmeinungen und Aussagen zum niederländischen Steuerverfahren ohne Belang. Im Lichte des Ziels und Zwecks der internationalen Steueramtshilfe kann Ziff. XVI lit. a des Protokolls zum DBA CH-NL deshalb nicht anders verstanden werden, als dass die Formulierung "alle verfügbaren Mittel" inhaltlich nicht weiter geht als "alle üblichen Mittel", sondern die Bedeutung dieselbe ist.
5.5.2. Dies wird auch bestätigt durch die indifferente Verwendung von unterschiedlichen Formulierungen in der bundesrätlichen Botschaft zur Genehmigung eines Doppelbesteuerungsabkommens zwischen der Schweiz und den Niederlanden vom 25. August 2010 (BBl 2010 5787 ff.). So führt die deutsche Fassung der Botschaft aus (BBl 2010 5800) : "Zudem wird festgehalten, dass der ersuchende Staat gehalten ist, seine eigenen Untersuchungsmöglichkeiten auszuschöpfen, bevor er den anderen Staat um Informationen ersucht." Rein grammatikalisch entspricht dies eher der Ausschöpfung aller verfügbaren Mittel. Bei der Kommentierung der einzelnen Bestimmungen führt die Botschaft dagegen aus (BBl 2010 5802) : "Die Vertragsstaaten sind demnach gehalten ein Auskunftsersuchen erst dann zu stellen, wenn sie sämtliche in ihrem innerstaatlichen Steuerverfahrensrecht üblichen Mittel der Informationsermittlung ausgeschöpft haben." Die französische Fassung der Botschaft hält diesbezüglich zunächst fest (Message concernant l'approbation d'une convention entre la Suisse et les Pay-Bas contre les doubles impositions du 25 aout 2010, BBl 2010 5243 ff., 5257) : "En outre, l'Etat requérant est tenu d'épuiser au préalable les sources habituelles de renseignements prévues par sa procédure fiscale interne avant de présenter une demande de renseignements à l'autre Etat." Zu Art. 26 DBA CH-NL und dem Protokoll führt die Botschaft aus (BBl 2010 5259) : "Le principe de subsidiarité implique que la demande de renseignements fasse état de l'épuisement des moyens dont dispose l'Etat requérant."
5.5.3. Im Übrigen wurde gemäss Botschaft zum DBA CH-NL das aDBA CH-NL vom 12. November 1951 (AS 1952 179) durch das geltende DBA CH-NL ersetzt, um wie vom Bundesrat am 13. März 2009 beschlossen, dem neuen OECD-Standard und dem entsprechenden OECD-Musterabkommen zur Vermeidung der Doppelbesteuerung auf dem Gebiete der Steuern vom Einkommen und Vermögen (OECD-MA) gerecht zu werden. Zentral war in diesem Zusammenhang die Übernahme des OECD-Standards in der Amtshilfe in Steuersachen bzw. einer Art. 26 OECD-MA entsprechenden Bestimmung. In diesem Rahmen wurde auch das Subsidiaritätsprinzip erwähnt, welches es nun zu berücksichtigen gelte. Von einem gegenüber dem OECD-Standard abweichenden Verständnis des Subsidiaritätsprinzips ist dagegen nicht die Rede (BBl 2010 5787 f., 5790 f., 5800). Der Kommentar zum OECD-MA vom 22. Juli 2010, welcher rechtsprechungsgemäss bei der Auslegung zu berücksichtigen ist (Urteil 2C_209/2017 vom 16. Dezember 2019 E. 3.4.1 mit Hinweisen [Urteil zur Publikation vorgesehen]; <ref-ruling> E. 8.2.3 S. 140 mit Hinweisen), hält diesbezüglich fest (Model Tax Convention on Income and on Capital, Volume I and II, OECD Committee on Fiscal Affairs, 2012, C- (26) -4 Ziff. 9) : "The rule laid down in paragraph 1 allows information to be exchanged in three different ways: a) on request, with a special case in mind, it being understood that the regular sources of information available under the internal taxation procedure should be relied upon in the first place before a request for information is made to the other State." Die Formulierung "regular" ist mit "gewöhnlich" oder "üblich" gleichzusetzen. Auch daraus folgt, dass der relevante niederländische Protokolltext inhaltlich dieselbe Bedeutung hat wie der französische Text. Der neueste OECD-Kommentar zum OECD-MA (in der Fassung vom 21. November 2017) lautet diesbezüglich gleich (Model Tax Convention on Income and on Capital, Volume I and II, OECD Committee on Fiscal Affairs, 2019, C- (26) -4 Ziff. 9).
5.5.4. Aufschlussreich ist in diesem Zusammenhang auch der Blick auf das OECD-Musterabkommen über den Informationsaustausch in Steuersachen vom April 2002 (TIEA-MA [Model Tax Information Exchange Agreement]; <https://www.oecd.org/tax/exchange-of-tax-information/ taxinformationexchangeagreementstieas.htm>; besucht am 27. Mai 2020). Das TIEA-MA ist als Musterabkommen nicht verbindlich, repräsentiert jedoch ebenfalls den OECD-Standard und insofern die weitgehend vorbestehende Praxis der Staaten für einen effektiven Informationsaustausch in Steuersachen (vgl. Ziff. I/3 und 4, Introduction, TIEA-MA). Gemäss Art. 5 Abs. 5 lit. g des TIEA-MA soll der ersuchende Staat im Amtshilfegesuch unter anderem folgende Angaben machen: "a statement that the applicant Party has pursued all means available in its own territory to obtain the information, except those that would give rise to disproportionate difficulties." Die entsprechende, französische Formulierung lautet: "une declaration précisant que la partie requérante a utilisé pour obtenir les renseignements tous les moyens disponibles sur son propre territoire, hormis ceux qui susciteraient des difficultés disproportionnées." Der Wortlaut an sich spricht für das Erfordernis der Ausschöpfung aller verfügbaren Mittel. Im von der OECD herausgegebenen Kommentar zum TIEA-MA wird diesbezüglich jedoch ausgeführt: "While paragraph 5 contains important procedural requirements that are intended to ensure that fishing expeditions do not occur, subparagrahps a) through g) nevertheless need to be interpreted liberally in order not to frustrate effective exchange of information." [...] Sub-paragraph g) is explained by the fact that, depending on the tax system of the requested Party, a request for information may place an extra burden on the administrative machinery of the requested Party. Therefore, a request should only be contemplated if an applicant Party has no convenient means to obtain the information available within its own jurisdiction. In as far as other means are still available in the applicant Party, the statement prescribed in sub-paragraph g) should explain that these would give rise to disproportionate difficulties. In this last case an element of proportionality plays a role. It should be easier for the requested Party to obtain the information sought after, than for the applicant Party. For example, obtaining information from one supplier in the requested Party may lead to the same information as seeking information from a large number of buyers in the applicant Party" (Exchange of Information on Request, Handbook for Peer Reviews 2016-2020, Global Forum on Transparency and Exchange of Information for tax purposes, OECD, 3. Aufl. 2016, S. 144 ff. Rz. 57 und 63; <https://www.oecd.org/tax/transparency/about-the-global-forum/publications>; besucht am 27. Mai 2020). Art. 5 Abs. 5 lit. g TIEA-MA soll demnach grosszügig ausgelegt werden, und zwar zugunsten einer wirksamen bzw. effektiven Steueramtshilfe (vgl. ANDREA OPEL, Neuausrichtung der schweizerischen Abkommenspolitik in Steuersachen: Amtshilfe nach dem OECD-Standard, 2015, S. 342 f.). Wie das angeführte Beispiel verdeutlicht, geht es primär darum, den ersuchten Staat nicht mit (unnötigen) Amtshilfegesuchen zu belasten, wenn die gesuchten Informationen mit geeigneten Mitteln und ohne grössere Umtriebe, sprich genauso gut im Territorium des ersuchenden Staates beschafft werden können. Das Verständnis orientiert sich auch hier am Ziel und Zweck einer effektiven, also wirksamen und damit auch speditiven Steueramtshilfe. Der ersuchende Staat soll demzufolge gerade nicht alle im rein grammatikalischen Sinne verfügbaren Mittel ausschöpfen müssen, bevor er ein Amtshilfegesuch stellen kann. Die Anforderungen an die Ausschöpfung der innerstaatlichen Mittel gehen deshalb bei teleologischem Verständnis nicht über die Ergreifung der üblichen Mittel hinaus. Zudem geht auch der Kommentar zum OECD-MA bzw. zu dessen Art. 26, welcher den Rahmen der Steueramtshilfe absteckt, bloss von den "regular" bzw. "üblichen" Mitteln aus. Entgegen den Beschwerdeführern ist das Protokoll zum DBA CH-NL auch nicht strenger als Art. 5 Abs. 5 lit. g TIEA-MA, weil es keine ausdrückliche Formulierung bezüglich "unverhältnismässiger Schwierigkeiten" enthält. Ziff. XVI lit. a des Protokolls zum DBA CH-NL orientiert sich als integraler Bestandteil dieses DBA wie Art. 26 desselben am OECD-Standard. Entscheidend ist demnach die Gewährleistung einer effektiven Steueramtshilfe, weshalb vom ersuchenden Staat auch ohne einen solchen Zusatz kein zu befürchtender, unverhältnismässiger Aufwand (bei Ausschöpfung der eigenen Mittel) als Bedingung für ein Steueramtshilfegesuch vorausgesetzt werden darf.
5.6. Insbesondere schweizerische Bankdaten, um welche vorliegend ersucht wird, sind aufgrund der (schweizerischen) gesetzlichen Rahmenbedingungen für die niederländischen Steuerbehörden nicht greifbar. Die ESTV durfte deshalb darauf vertrauen, dass der BD das Subsidiaritätsprinzip eingehalten hat (vgl. Urteil 2C_893/2015 vom 16. Februar 2017 E. 11.2, nicht publ. in: BGE <ref-ruling>). Auch durfte sich die ESTV gemäss Vertrauensprinzip (vgl. dazu <ref-ruling> E. 3.3.2 S. 211; <ref-ruling> E. 8.7.1 S. 221 f.) im Lichte des genannten Auslegungsergebnisses auf die Erklärung im Amtshilfegesuch, wonach die üblichen Mittel erschöpft seien, sowie auf die Zusicherung des BD, dass "auch ohne Eröffnung einer Informationsverfügung alle (üblichen) Mittel ausgeschöpft sind", verlassen (wobei vorliegend unbestrittenermassen eine Informationsverfügung erlassen worden war, nur war diese zum Zeitpunkt des Amtshilfegesuchs noch nicht in Rechtskraft erwachsen).
5.7. Demzufolge ist vorliegend weder das Subsidiaritätsprinzip bzw. Ziff. XVI lit. a des Protokolls zum DBA CH-NL noch das völkerrechtliche Vertrauensprinzip verletzt worden. Das vorinstanzliche Urteil ist somit völkerrechtskonform.
6.
6.1. Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen.
6.2. Dem Verfahrensausgang entsprechend haben die Beschwerdeführer die Gerichtskosten zu gleichen Teilen unter solidarischer Haftung zu tragen (Art. 65 und Art. 66 Abs. 1 und 5 BGG). Eine Parteientschädigung ist nicht geschuldet.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten des bundesgerichtlichen Verfahrens von Fr. 5'000.-- werden den Beschwerdeführern auferlegt. Letztere tragen diese Kosten zu gleichen Teilen unter solidarischer Haftung.
3.
Dieses Urteil wird den Verfahrensbeteiligten und dem Bundesverwaltungsgericht, Abteilung I, schriftlich mitgeteilt.
Lausanne, 17. August 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Quinto