Sachverhalt: A. A._ und B._ als Eigentümer der Liegenschaft Nr. xxx im Grundbuch Tobel-Tägerschen/TG erhoben im Jahre 2013 Einsprache gegen ein Bauprojekt des Ehepaars C.D._ und D.D._ auf der nachbarschaftlichen Liegenschaft Nr. yyy. Am 4. November 2013 wies die Gemeinde Tobel-Tägerschen die Einsprache ab und erteilte die Baubewilligung. Dagegen erhoben A._ und B._ Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Am 7. Januar 2014 beantragten die Ehegatten C.D._ und D.D._ bei der Gemeinde eine vorzeitige Baufreigabe, die am 15. Januar 2014 bewilligt wurde. Auch dagegen rekurrierten A._ und B._. Am 29. August 2014 wies das Departement beide Rekurse in einem einzigen Entscheid ab und auferlegte den Rekurrenten eine Verfahrensgebühr von insgesamt Fr. 2'500.--. B. Dagegen führten A._ und B._ Beschwerde beim Verwaltungsgericht des Kantons Thurgau, wobei sie nebst den Anträgen in der Sache ausdrücklich mit Blick auf die Anfechtung der vorzeitigen Baufreigabe zur Hälfte auch die Kostenauflage im Betrag von Fr. 1'250.-- anfochten. Mit Entscheid vom 4. Mai 2016 wies das Verwaltungsgericht die Beschwerde integral ab. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 4. Juli 2016 an das Bundesgericht beantragen A._ und B._, das Urteil des Verwaltungsgerichts aufzuheben und ihnen für das Verfahren betreffend vorzeitige Baufreigabe vor dem Departement keine Kosten aufzuerlegen bzw. diese auf das gesetzliche Minimum von Fr. 50.-- herabzusetzen. Zur Begründung machen sie im Wesentlichen geltend, das Departement habe im fraglichen Verfahren gar keinen Aufwand getätigt. Mit dem Entscheid in der Sache bzw. der vorzeitigen Realisierung des Bauprojekts sei der Rekurs gegen die Erteilung der vorzeitigen Baubewilligung gegenstandslos geworden. Eine Kostenauflage sei deshalb insbesondere mit Blick auf die für Gebühren massgeblichen Grundsätze wie das Kostendeckungs- und Äquivalenzprinzip willkürlich und rechtsungleich und verstosse auch gegen weitere Verfassungsrechte. Das Departement für Bau und Umwelt des Kantons Thurgau, die Politische Gemeinde Tobel-Tägerschen und das Verwaltungsgericht des Kantons Thurgau schliessen auf Abweisung der Beschwerde. C.D._ und D.D._ reichten dem Bundesgericht keine Stellungnahme ein. Mit Eingabe vom 22. September 2016 äusserten sich A._ und B._ nochmals zur Sache.