Bundesgericht
Tribunal fédéral
Tribunale federale
Tribunal federal

{T 0/2}

1C 23/2014, 1C 25/2014

Urteil vom 24. März 2015

I. öffentlich-rechtliche Abteilung

Besetzung
Bundesrichter Merkli, präsidierendes Mitglied,
Bundesrichter Karlen, Kneubühler,
Gerichtsschreiberin Gerber.

Verfahrensbeteiligte
1. A.________,
2. B.________,
beide vertreten durch Rechtsanwalt Urs Pfister,
Beschwerdeführer,

gegen

1C 23/2014
1. C.________,
2. D.________,
3. E.________,
4. F.________,
vertreten durch Samuel Waldburger,
Beschwerdegegner 1,

und

1C 25/2014
G.________,
vertreten durch Rechtsanwalt Simon Kehl,
Beschwerdegegner 2,

Baubewilligungskommission Walzenhausen, 9428 Walzenhausen,
Departement Bau und Umwelt Appenzell Ausserrhoden,
Kasernenstrasse 17A, 9102 Herisau.

Gegenstand
Baubewilligung,

Beschwerden gegen die Urteile vom 24. April 2013 des Obergerichts Appenzell Ausserrhoden, 4. Abteilung.

Sachverhalt:

A.
Mit Baugesuch vom 25. März 2009 ersuchten A.________ und B.________ um die Bewilligung eines Einfamilienhaus-Neubaus auf der Parzelle Nr. 1407 in Lachen, Walzenhausen. Die Parzelle liegt gemäss Zonenplan und Baureglement der Gemeinde Walzenhausen vom 16. September 1997 in der Wohnzone W1. Die Behandlung des Baugesuchs wurde sistiert, bis die vom Gemeinderat für das fragliche Gebiet ("Sonnhalde") erlassene Planungszone Anfang 2010 ausgelaufen war.
Vom 13. Januar bis 1. Februar 2010 wurde das Baugesuch öffentlich aufgelegt. Dagegen erhob am 29. Januar 2010 die "Interessengemeinschaft Privatfahrweg altes Schulhaus Lachen-Derbelen", bestehend aus C.________, D.________, E.________, H. und I. J.________, K.________ sowie F.________, Einsprache. Am 30. Januar 2010 erhob auch G.________ Einsprache bei der Baubewilligungskommission Walzenhausen.
Mit Bau- und Einspracheentscheid vom 30. April 2010 bewilligte die Baubewilligungskommission Walzenhausen das Bauvorhaben und wies die dagegen gerichteten Einsprachen ab. Die privatrechtlichen Einwendungen wurden auf den Zivilrechtsweg verwiesen.

B.
Dagegen erhoben C.________, D.________, E.________, H. und I. J.________ sowie F.________ einerseits und G.________ andererseits am 21. Mai 2010 in getrennten Eingaben Rekurs beim Departement für Bau und Umwelt des Kantons Appenzell Ausserrhoden (DBU). Dieses wies die Rekurse am 5. November 2010 im Sinne der Erwägungen ab, soweit darauf eingetreten wurde. Es hielt in den Erwägungen fest, dass das Bauvorhaben die maximale Ausnützung von 0.4 für die Wohnzone W1 gemäss den vom 10. März bis 9. April 2010 öffentlich aufgelegten revidierten Zonenvorschriften um rund ein Drittel überschreite; diese seien jedoch noch nicht in Kraft getreten und könnten deshalb nicht angewendet werden.
Dagegen führten C.________, D.________, E.________ und F.________ am 8. Dezember sowie G.________ am 15. Dezember 2010 Beschwerde an das Obergericht Appenzell Ausserrhoden.

C.
Mit Urteil vom 9. Mai 2011 hiess das Kantonsgericht Appenzell Ausserrhoden die Klage von G.________ und Mitbeteiligten im wesentlichen gut und verbot A.________ und B.________, den von der Staatsstrasse Nr. 54 zur Bauparzelle führenden Fahrweg als Zufahrt zu benutzen. Am 23. April 2012 wies die zivilrechtliche Abteilung des Obergerichts die dagegen erhobene Berufung ab.
Das Bundesgericht hiess die dagegen erhobene Beschwerde am 21. Dezember 2012 gut und wies die Klage von G.________ und Mitbeteiligten ab (Urteil 5A 602+625/2012). Es entschied, dass ein Fahrrecht zu allgemeinen Wohnzwecken bestehe und dieses durch die Erstellung des zusätzlichen Wohnhauses nicht in unzulässiger Weise mehrbelastet werde.

D.
Das vor der verwaltungsrechtlichen Abteilung des Obergerichts hängige Verfahren betreffend Baubewilligung war bis zum Abschluss des zivilrechtlichen Verfahrens formlos sistiert worden und wurde auf Antrag von A.________ und B.________ vom 28. Dezember 2012 wieder aufgenommen.
Da am 25. November 2012 das neue Baureglement der Gemeinde Walzenhausen in der kommunalen Abstimmung angenommen und am 5. Februar 2013 vom Regierungsrat genehmigt worden war (im Folgenden: BauR-2013), erhielten die Parteien Gelegenheit, dazu Stellung zu nehmen. D.________ zog seine Beschwerde am 12. März 2013 zurück.
Am 24. April 2013 führte das Obergericht einen Augenschein durch. Es hiess gleichentags die Beschwerden in zwei gesonderten Urteilen gut und hob die Rekursentscheide des DBU auf, soweit damit der Bau- und Einspracheentscheid der Baubewilligungskommission vom 30. April 2010 bestätigt wurde. Soweit die Beschwerde im Namen von D.________ erhoben worden war, wurde sie infolge Rückzugs vom Gerichtsprotokoll abgeschrieben.

E.
Gegen beide Urteile haben A.________ und B.________ am 13. Januar 2014 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben (1C 23 und 25/2014). Sie beantragen, die Urteile des Obergerichts vom 24. April 2013 seien aufzuheben und die Beschwerden von C.________ und Mitbeteiligten sowie von G.________ kosten- und entschädigungspflichtig abzuweisen. Eventualiter sei die Sache zur nochmaligen Beurteilung in der Sache, subeventualiter zur Neuverlegung der amtlichen und ausseramtlichen Kosten, an die Vorinstanz zurückzuweisen. In prozessualer Hinsicht beantragen sie, die Beschwerdeverfahren seien zu vereinigen.

F.
C.________ und Mitbeteiligte (Beschwerdegegner 1) beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei; eventualiter sei die Sache an das Obergericht zurückzuweisen zur Klärung der offenen Frage, ob der Fahrweg altes Schulhaus Lachen-Derbelen als Zufahrt für eine Überbauung der Parzelle Nr. 1407 ausreichend sei. G.________ (Beschwerdegegner 2) schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
D.________ teilt mit, dass er nicht Verfahrenspartei sei, da seine Beschwerde vom Obergericht infolge Rückzugs vom Gerichtsprotokoll abgeschrieben worden sei.
Der Regierungsrat teilt die Auffassung der Beschwerdeführer, dass das Urteil gegen Art. 9
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 9 Schutz vor Willkür und Wahrung von Treu und Glauben - Jede Person hat Anspruch darauf, von den staatlichen Organen ohne Willkür und nach Treu und Glauben behandelt zu werden.
BV verstosse, ohne formell einen Antrag zu stellen. Das Obergericht hat auf eine Vernehmlassung verzichtet. Die Gemeinde Walzenhausen hat sich nicht vernehmen lassen.
Im weiteren Schriftenwechsel halten die Parteien an ihren Anträgen fest.

Erwägungen:

1.
Beide Beschwerden betreffen dasselbe Baugesuch und werfen die gleichen Rechtsfragen auf. Es rechtfertigt sich daher, die Verfahren zu vereinigen.

2.
Gegen die kantonal letztinstanzlichen Endentscheide des Obergerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 82 Grundsatz - Das Bundesgericht beurteilt Beschwerden:
a  gegen Entscheide in Angelegenheiten des öffentlichen Rechts;
b  gegen kantonale Erlasse;
c  betreffend die politische Stimmberechtigung der Bürger und Bürgerinnen sowie betreffend Volkswahlen und -abstimmungen.
, 86 Abs. 1
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 86 Vorinstanzen im Allgemeinen - 1 Die Beschwerde ist zulässig gegen Entscheide:
1    Die Beschwerde ist zulässig gegen Entscheide:
a  des Bundesverwaltungsgerichts;
b  des Bundesstrafgerichts;
c  der unabhängigen Beschwerdeinstanz für Radio und Fernsehen;
d  letzter kantonaler Instanzen, sofern nicht die Beschwerde an das Bundesverwaltungsgericht zulässig ist.
2    Die Kantone setzen als unmittelbare Vorinstanzen des Bundesgerichts obere Gerichte ein, soweit nicht nach einem anderen Bundesgesetz Entscheide anderer richterlicher Behörden der Beschwerde an das Bundesgericht unterliegen.
3    Für Entscheide mit vorwiegend politischem Charakter können die Kantone anstelle eines Gerichts eine andere Behörde als unmittelbare Vorinstanz des Bundesgerichts einsetzen.
lit. d und 90 BGG). Die Beschwerdeführer sind als Baugesuchsteller und Grundstückseigentümer zur Beschwerde legitimiert (Art. 89 Abs. 1
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 89 Beschwerderecht - 1 Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist berechtigt, wer:
1    Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist berechtigt, wer:
a  vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat;
b  durch den angefochtenen Entscheid oder Erlass besonders berührt ist; und
c  ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat.
2    Zur Beschwerde sind ferner berechtigt:
a  die Bundeskanzlei, die Departemente des Bundes oder, soweit das Bundesrecht es vorsieht, die ihnen unterstellten Dienststellen, wenn der angefochtene Akt die Bundesgesetzgebung in ihrem Aufgabenbereich verletzen kann;
b  das zuständige Organ der Bundesversammlung auf dem Gebiet des Arbeitsverhältnisses des Bundespersonals;
c  Gemeinden und andere öffentlich-rechtliche Körperschaften, wenn sie die Verletzung von Garantien rügen, die ihnen die Kantons- oder Bundesverfassung gewährt;
d  Personen, Organisationen und Behörden, denen ein anderes Bundesgesetz dieses Recht einräumt.
3    In Stimmrechtssachen (Art. 82 Bst. c) steht das Beschwerderecht ausserdem jeder Person zu, die in der betreffenden Angelegenheit stimmberechtigt ist.
BGG). Auf die rechtzeitig erhobene Beschwerde (Art. 100 Abs. 1
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 100 Beschwerde gegen Entscheide - 1 Die Beschwerde gegen einen Entscheid ist innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung beim Bundesgericht einzureichen.
1    Die Beschwerde gegen einen Entscheid ist innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung beim Bundesgericht einzureichen.
2    Die Beschwerdefrist beträgt zehn Tage:
a  bei Entscheiden der kantonalen Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen;
b  bei Entscheiden auf den Gebieten der internationalen Rechtshilfe in Strafsachen und der internationalen Amtshilfe in Steuersachen;
c  bei Entscheiden über die Rückgabe eines Kindes nach dem Europäischen Übereinkommen vom 20. Mai 198089 über die Anerkennung und Vollstreckung von Entscheidungen über das Sorgerecht für Kinder und die Wiederherstellung des Sorgerechts oder nach dem Übereinkommen vom 25. Oktober 198090 über die zivilrechtlichen Aspekte internationaler Kindesentführung;
d  bei Entscheiden des Bundespatentgerichts über die Erteilung einer Lizenz nach Artikel 40d des Patentgesetzes vom 25. Juni 195492.
3    Die Beschwerdefrist beträgt fünf Tage:
a  bei Entscheiden der kantonalen Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen im Rahmen der Wechselbetreibung;
b  bei Entscheiden der Kantonsregierungen über Beschwerden gegen eidgenössische Abstimmungen.
4    Bei Entscheiden der Kantonsregierungen über Beschwerden gegen die Nationalratswahlen beträgt die Beschwerdefrist drei Tage.
5    Bei Beschwerden wegen interkantonaler Kompetenzkonflikte beginnt die Beschwerdefrist spätestens dann zu laufen, wenn in beiden Kantonen Entscheide getroffen worden sind, gegen welche beim Bundesgericht Beschwerde geführt werden kann.
6    ...93
7    Gegen das unrechtmässige Verweigern oder Verzögern eines Entscheids kann jederzeit Beschwerde geführt werden.
BGG) ist daher einzutreten.

3.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 95 Schweizerisches Recht - Mit der Beschwerde kann die Verletzung gerügt werden von:
a  Bundesrecht;
b  Völkerrecht;
c  kantonalen verfassungsmässigen Rechten;
d  kantonalen Bestimmungen über die politische Stimmberechtigung der Bürger und Bürgerinnen und über Volkswahlen und -abstimmungen;
e  interkantonalem Recht.
BGG beruht (Art. 105
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 105 Massgebender Sachverhalt - 1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat.
1    Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat.
2    Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht.
3    Richtet sich die Beschwerde gegen einen Entscheid über die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung, so ist das Bundesgericht nicht an die Sachverhaltsfeststellung der Vorinstanz gebunden.95
und Art. 97 Abs. 1
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 97 Unrichtige Feststellung des Sachverhalts - 1 Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann.
1    Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann.
2    Richtet sich die Beschwerde gegen einen Entscheid über die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung, so kann jede unrichtige oder unvollständige Feststellung des rechtserheblichen Sachverhalts gerügt werden.86
BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 99 - 1 Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt.
1    Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt.
2    Neue Begehren sind unzulässig.
BGG).
Die Beschwerdeführer haben zahlreiche Unterlagen eingereicht; die Beschwerdegegner machen geltend, es handle sich zum Teil um unzulässige Noven.
Die meisten dieser Unterlagen sind Doppel von bereits in den vorinstanzlichen Akten liegenden Dokumenten und damit keine Noven. Unzulässig sind dagegen die erst nach dem angefochtenen Entscheid entstandenen Dokumente, da es sich insoweit um "echte" Noven handelt (vgl. BGE 133 IV 342 E. 2.1 S. 344). Zur Zulässigkeit der übrigen Dokumente wird erst Stellung zu nehmen sein, falls sie sich für die Entscheidfindung als relevant erweisen sollten.
Die Sachverhaltsrügen der Beschwerdeführer werden aufgrund ihres engen Zusammenhangs mit den materiellen Rügen mit diesen gemeinsam behandelt.

4.
Es ist unstreitig, dass das Bauvorhaben die nach Art. 18 BauR-2013 zulässige Ausnützung in der Wohnzone W1 überschreitet. Streitig ist nur, ob das Obergericht das im Zeitpunkt seines Urteils am 24. April 2013 geltende neue Reglement anwenden durfte, obwohl dieses im Zeitpunkt der Rekursentscheide des DBU (am 5. November 2010) noch nicht in Kraft war.

4.1. Das Obergericht bejahte dies gestützt auf Art. 50 Abs. 1 BauR 2013, wonach das Reglement nach Annahme durch die Stimmberechtigten mit der Genehmigung durch den Regierungsrat in Kraft tritt und alle Baugesuche, die in diesem Zeitpunkt noch nicht rechtskräftig bewilligt sind, dem neuen Recht unterstehen. Eine praktisch gleichlautende Bestimmung habe schon Art. 55 Abs. 1 BauR-1996/97 vorgesehen; auch Art. 124 des kantonalen Gesetzes über die Raumplanung und das Baurecht vom 12. Mai 2003 (BauG/AR; GS 721.1) kenne eine entsprechende Regelung.
Das Obergericht führte aus, dass es nach Lehre und Rechtsprechung in erster Linie Sache des Gesetzgebers sei, mit übergangsrechtlichen Bestimmungen den zeitlichen Geltungsbereich der alten von demjenigen der neuen Rechtsordnung abzugrenzen und zu bestimmen, ob und gegebenenfalls in welchen Fällen das alte Recht nachwirke und welches Recht in zum Zeitpunkt der Rechtsänderung hängigen erstinstanzlichen Verfahren oder Rechtsmittelverfahren anzuwenden sei. Bei der Ausgestaltung einer angemessenen Übergangsregelung stehe dem Gesetzgeber ein weiter Spielraum des Ermessens offen, unter Beachtung des Grundsatzes rechtsgleicher Behandlung, des Verhältnismässigkeitsprinzips, des Willkürverbots und des Vertrauensgrundsatzes (BGE 128 I 92 E. 4 S. 98 f. mit Hinweisen).
Es gelangte in seinen Erwägungen zum Schluss, dass der spezialgesetzlich durch Art. 50 Abs. 1 BauR-2013 zwingend gebotenen Anwendung der teilrevidierten Zonenvorschriften (Art. 18) auf das streitige Bauvorhaben keinerlei verfassungsmässige Hindernisse entgegenstehen.

4.2. Streitig ist somit die Anwendung einer kommunalen Übergangsregelung (Art. 50 Abs. 1 BauR-2013) im obergerichtlichen Verfahren. Die sich in diesem Zusammenhang stellenden grundrechtlichen Fragen prüft das Bundesgericht nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und genügend begründet worden ist (Rügeprinzip; Art. 106 Abs. 2
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 106 Rechtsanwendung - 1 Das Bundesgericht wendet das Recht von Amtes wegen an.
1    Das Bundesgericht wendet das Recht von Amtes wegen an.
2    Es prüft die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist.
BGG; BGE 133 II 249 E. 1.4.2 S. 254 mit Hinweisen).

5.
Die Beschwerdeführer rügen zunächst, das Obergericht habe in seiner Funktion als Verwaltungsgericht gemäss den Art. 54 ff. des Verwaltungsrechtspflegegesetzes des Kantons Appenzell Ausserrhoden vom 9. September 2002 [VRPG/AR; GS 143.1] zu prüfen, ob der Entscheid der Vorinstanz, d.h. des DBU, richtig sei. Dabei habe es nur ausnahmsweise volle Kognition; in der Regel sei es auf die Prüfung von Rechtsverletzungen und Sachverhaltsrügen beschränkt (Art. 56 Abs. 1-3 VRPG/AR). Daraus ergebe sich, dass das Obergericht keine Vorschriften zur Anwendung bringen könne, die im Zeitpunkt des Entscheides des DBU noch nicht rechtsgültig waren. Das DBU entscheide als letzte Instanz mit voller Kognition. Die kommunale Übergangsbestimmung von Art. 50 BauR-2013 könne daher nur bis zum Baurekursverfahren Anwendung finden, nicht aber im gerichtlichen Verfahren. Die gegenteilige Auffassung des Obergerichts sei unhaltbar und damit willkürlich (Art. 9
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 9 Schutz vor Willkür und Wahrung von Treu und Glauben - Jede Person hat Anspruch darauf, von den staatlichen Organen ohne Willkür und nach Treu und Glauben behandelt zu werden.
BV).

5.1. Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (BGE 136 I 316 E. 2.2.2 S. 318 f. mit Hinweisen).

5.2. Art. 54 Abs. 1 VRPG/AR umschreibt das Anfechtungsobjekt vor Obergericht (letztinstanzliche Entscheide einer Verwaltungsbehörde) und enthält jedenfalls keine ausdrückliche Aussage zum anwendbaren Recht. Die Auslegung des Obergerichts, wonach es Aufgabe des materiell-rechtlich zuständigen Gemeindegesetzgebers sei, den zeitlichen Geltungsbereich des kommunalen Rechts zu bestimmen, trägt der Autonomie der Gemeinden auf dem Gebiet des Bau- und Planungsrechts Rechnung und ist jedenfalls unter Willkürgesichtspunkten nicht zu beanstanden.
Daran ändert auch die auf Rechts- und Sachverhaltsfragen begrenzte Kognition des Obergerichts nach Art. 56 Abs. 1 VRPG/AR nichts: Sollten sich nach neuem Recht Ermessensfragen stellen (was vorliegend nicht der Fall war), hätte das Verwaltungsgericht die Möglichkeit, die Sache zu neuer Prüfung an das Departement zurückzuweisen.

6.
Die Beschwerdeführer machen weiter geltend, aufgrund der langen Verfahrensdauer verstosse es gegen Treu und Glauben (Art. 5 Abs. 3
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 5 Grundsätze rechtsstaatlichen Handelns - 1 Grundlage und Schranke staatlichen Handelns ist das Recht.
1    Grundlage und Schranke staatlichen Handelns ist das Recht.
2    Staatliches Handeln muss im öffentlichen Interesse liegen und verhältnismässig sein.
3    Staatliche Organe und Private handeln nach Treu und Glauben.
4    Bund und Kantone beachten das Völkerrecht.
BV), Art. 18 i.V.m. Art. 50 BauR-2013 noch im obergerichtlichen Verfahren auf ihr Bauvorhaben anzuwenden.

6.1. Das Obergericht habe übersehen, dass sie bereits im Jahr 2005 ein Bauermittlungsgesuch und anschliessend (am 5. Dezember 2005) ein Baugesuch eingereicht hatten, das am 28. Dezember 2006 von der Baubehörde bewilligt worden sei. Die Baubewilligung sei am 20. August 2007 auf Rekurs von H.________ (Rechtsvorgänger des Beschwerdegegners 2) vom DBU aufgehoben und die dagegen erhobene Beschwerde am 28. Mai 2008 gerichtlich abgewiesen worden. Das heute streitige Baugesuch sei - von der Dachgestaltung und wenigen untergeordneten Details abgesehen - dasselbe Vorhaben, für das schon 2005 ein Baugesuch eingereicht worden sei. Es lasse sich mit dem Grundsatz von Treu und Glauben nicht vereinbaren, für die Beurteilung eines Baugesuchs Bestimmungen zur Anwendung zu bringen, die erst 7 1/2 Jahre nach Gesuchseinreichung rechtsgültig geworden seien. Das Obergericht habe dem ersten Baugesuch von 2005 zu Unrecht keine Bedeutung beigemessen; insofern liege eine unvollständige Sachverhaltsfeststellung vor.
Wie die Beschwerdeführer jedoch selbst vorbringen, war ihr erstes Baugesuch nicht bewilligungsfähig; die Baubewilligung wurde daher vom DBU ersatzlos aufgehoben, ohne die Sache an die Gemeinde (z.B. zur Prüfung von Auflagen und Bedingungen) zurückzuweisen. Damit war das Baubewilligungsverfahren abgeschlossen. Mit dem Baugesuch 2009 wurde daher ein neues Verfahren eröffnet. Da damals noch eine Planungszone galt, durfte das Baugesuch erst nach deren Aufhebung Anfang 2010 behandelt und öffentlich aufgelegt werden (vgl. dazu auch unten E. 7.3).
Unter diesen Umständen war das Obergericht nicht verpflichtet, das Baugesuch 2005 zu berücksichtigen. Es durfte vielmehr die Verfahrensdauer ab der öffentlichen Auflage des Baugesuchs im Anfang 2010 berechnen, d.h. davon ausgehen, dass die zivil- und öffentlich-rechtlichen Verfahren insgesamt nur wenig mehr als drei Jahre in Anspruch genommen haben.

6.2. Die Beschwerdeführer rügen in diesem Zusammenhang, es sei nicht statthaft, ihnen die Dauer des Verfahrens anzulasten: Nachdem das Kantonsgericht am 9. Mai 2011 entschieden habe, die rechtliche Erschliessung sei nicht sichergestellt, sei es offensichtlich geboten gewesen, das Verfahren betreffend die Baubewilligung zu sistieren, bis diese Frage geklärt gewesen sei. Andernfalls hätte das Obergericht die Beschwerde mit der gleichen Begründung (fehlende rechtliche Erschliessung) wie das Kantonsgericht geschützt, obwohl sich diese Begründung mit dem Urteil des Bundesgerichts vom 21. Dezember 2012 als unzutreffend erweisen sollte.
Das Obergericht hat jedoch mit dem Hinweis auf die Zustimmung der Beschwerdeführer zur formlosen Sistierung des Verfahrens bis zum Entscheid des Bundesgerichts lediglich belegen wollen, dass das Verfahren nicht von Seiten der Behörden oder der Einsprecher ungebührlich verzögert worden sei. Dies wird auch von den Beschwerdeführern nicht behauptet. Soweit sie eine Verletzung von Art. 58 Abs. 1 des Justizgesetzes vom 13. September 2010 (GS 145.31) geltend machen, weil ihnen das begründete Urteil erst sieben Monate seit der Eröffnung gestellt wurde, ist kein Zusammenhang dieser Verzögerung mit der Bewilligungsfähigkeit des Bauvorhabens zu erkennen.
Damit liegt keine Rechtsverzögerung seitens der Behörden oder der Einsprecher vor, welche die Anwendung des alten, der Bauherrschaft günstigeren Rechts gebieten würde (vgl. BGE 139 II 263 E. 8.2 S. 269 mit Hinweis). Ob die Verfahrensdauer im Zusammenhang mit weiteren Umständen zu einer Verletzung des Grundsatzes des Vertrauensschutzes (Art. 9
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 9 Schutz vor Willkür und Wahrung von Treu und Glauben - Jede Person hat Anspruch darauf, von den staatlichen Organen ohne Willkür und nach Treu und Glauben behandelt zu werden.
BV) führt, ist nachfolgend zu prüfen.

7.
Die Beschwerdeführer machen geltend, sie hätten darauf vertrauen dürfen, dass für ihr Bauvorhaben noch Zonenplan und Baureglement 1997 anwendbar sein würden. Dies sei ihnen von der Gemeinde zugesichert worden, insbesondere indem ihr Baugesuch ausdrücklich von der am 3. Januar 2007 verfügten Planungszone ausgenommen worden sei.

7.1. Das Obergericht ging davon aus, dass die Beschwerdeführer in Kenntnis der alt- und neurechtlich identischen kommunalen Übergangsbestimmungen sowie der hängigen Teilrevision des Baureglements für ihr neu aufgelegtes Bauvorhaben damit rechnen konnten und mussten, dass die revidierten, bezüglich Ausnützung verschärften Zonenvorschriften im Verlauf eines allfälligen Rechtsmittelverfahrens für ihr Bauvorhaben doch noch anwendbar werden könnten, auch wenn diese Gefahr durch das Auslaufen der Planungszone vorerst gebannt zu sein schien. Dass die Planungszone nicht verlängert worden sei, habe angesichts der alt- und neurechtlich klaren und identischen kommunalen Übergangsbestimmungen bei den ohnehin anwaltlich vertretenen Beschwerdeführern kein berechtigtes Vertrauen darauf begründen können, dass das neu aufgelegte Bauvorhaben auf Dauer von der verschärften Zonenvorschrift dispensiert sein könnte.

7.2. Die Beschwerdeführer rügen zunächst die Feststellung des Obergerichts als offensichtlich unrichtig, dass sie von Anfang an anwaltlich vertreten gewesen seien: Tatsächlich sei dies erst ab dem 12. Juli 2010 der Fall gewesen; bis dahin hätten sie alle Eingaben selbst erstellt und eingereicht. Sie seien insbesondere im Zeitpunkt der öffentlichen Auflage des revidierten Baureglements (vom 10. März bis 9. April 2010) noch nicht anwaltlich vertreten gewesen. Es sei daher verfehlt, wenn das Obergericht davon ausgehe, dass sie am 9. April 2010 Einsprache gegen Art. 50 BauR-2013 hätten erheben müssen.
Im angefochtenen Entscheid findet sich allerdings keine Aussage dieses Inhalts; insofern erscheint es fraglich, ob sich der Hinweis des Obergerichts auf die anwaltliche Vertretung auf den Zeitpunkt der öffentlichen Auflage der neuen Zonenvorschriften bezieht. Wie der Zusatz "ohnehin" belegt, mass das Obergericht der anwaltlichen Vertretung auch keine ausschlaggebende Bedeutung bei. Dies ist im vorliegenden Fall nicht zu beanstanden: Wie sich aus den Bauakten ergibt, ist der Beschwerdeführer 1 diplomierter Architekt und Raumplaner sowie Geschäftsführer eines Planungsbüros. Damit verfügt er im Bau- und Planungswesen über eigene Sachkunde und war nicht auf anwaltlichen Beistand angewiesen.

7.3. Entgegen der Auffassung der Beschwerdeführer ist keine Zusicherung der Gemeinde ersichtlich, dass für das Bauvorhaben noch das 1997 geltende Baureglement anwendbar sein würde:
Von der am 3. Januar 2007 verfügten Planungszone wurde ausdrücklich nur das "bewilligte Baugesuch Nr. 05-65 vom 7. Dezember 2005" ausgenommen. Für das neue Baugesuch vom 25. März 2009 lässt sich daraus keine Zusicherung ableiten. Dieses wurde denn auch von der Gemeinde bis zum Auslaufen der Planungszone Anfang 2010 sistiert, d.h. der Planungszone unterstellt. Die dagegen eingereichte Rechtsverweigerungsbeschwerde der Beschwerdeführer wies das DBU am 30. November 2009 ab, weil es sich um ein neues Baugesuch und nicht lediglich um eine Projektänderung handle.
Daran ändert auch die Zweckbestimmung der Planungszone nichts: Wurde diese - wie die Beschwerdeführer darlegen - nicht zur Sicherung der neuen Bauvorschriften, sondern zur Prüfung einer Auszonung des Gebiets erlassen, so konnte aus der Nichtverlängerung der Planungszone allenfalls abgeleitet werden, dass auf die zunächst beabsichtigte Auszonung verzichtet werde. Für die zeitliche Geltung der neuen Bauvorschriften war nicht die Planungszone, sondern die übergangsrechtliche Bestimmung des Baureglements massgeblich.

7.4. Art. 50 BauR-2013 sieht (wie bereits Art. 55 BauR-1996/1997) vor, dass Baugesuche, die im Zeitpunkt des Inkrafttretens der neuen Bestimmungen noch nicht rechtskräftig bewilligt sind, dem neuen Recht unterstehen. Die Beschwerdegegner haben dargelegt, dass fast alle kommunalen Baureglemente des Kantons eine gleichlautende Regelung enthalten.

7.4.1. Dies entspricht der älteren Rechtsprechung und Lehre, die im Bau- und Planungsrecht grundsätzlich das Recht im Zeitpunkt der Bewilligungserteilung durch die kantonal letzte Instanz für massgeblich erachtete (vgl. BGE 99 Ia 339 E. 2 S. 342; 107 Ib 133 E. 2a S. 137; Max Imboden/René A. Rhinow, Schweizerische Verwaltungsrechtsprechung, Band I, 6. Aufl. 1986, Nr. 15 II.a S. 96 f.; Fritz Gygi, Verwaltungsrecht, Bern 1986, S. 114; je mit Hinweisen).
Dieser Auffassung widersprach Alfred Kölz in seiner wegweisenden Abhandlung zum intertemporalen Verwaltungsrecht (ZSR 102/1983 II S. 100 ff, insbes. S. 206 ff.). Er kam zum Ergebnis, aufgrund des Vertrauensprinzips sei auf das zum Zeitpunkt der Einreichung des Baugesuchs geltende Recht abzustellen; diese Lösung sei auch vom öffentlichen Interesse her zu rechtfertigen, sofern flankierend Planungssicherungsinstrumente eingesetzt würden. Anknüpfungspunkt könne aber auch die erstinstanzliche Gesuchserledigung sein, mit Korrekturmöglichkeiten im Fall einer Verzögerung in der Behandlung des Baugesuchs. Dagegen sei die Anknüpfung an den Entscheid der letzten mit der Sache befassten Instanz mit dem Vertrauensprinzip unvereinbar, u.a. weil damit Verzögerungen der Entscheide im Rahmen des gesamten Instanzenzugs dem Baugesuchsteller überbunden würden (S. 208 f.; so auch Martin Straub, Das intertemporale Recht der Baubewilligung, Diss. Zürich 1976 S. 181).

7.4.2. Nach der neueren bundesgerichtlichen Rechtsprechung ist die Rechtmässigkeit von Verwaltungsakten (mangels einer speziellen übergangsrechtlichen Regelung) grundsätzlich nach der Rechtslage im Zeitpunkt ihres Ergehens zur beurteilen. Im Baubewilligungsverfahren ist daher i.d.R. der Zeitpunkt des erstinstanzlichen Entscheids der Baubehörde massgeblich (BGE 139 II 263 E. 6 S. 267 f. mit Hinweisen). Später eingetretene Rechtsänderungen sind nur ausnahmsweise zu berücksichtigen, wenn zwingende Gründe für die sofortige Anwendung des neuen Rechts sprechen (BGE 135 II 384 E. 2.3 S. 390; 125 II 591 E. 5e/aa S. 598; je mit Hinweisen; so auch Ulrich Häfelin/Georg Müller/Felix Uhlmann, Allgemeines Verwaltungsrecht, 6. Aufl., S. 71 Rz. 327; Pierre Tschannen/Ulrich Zimmerli/Markus Müller Allgemeines Verwaltungsrecht, 3. Aufl., S. 190 f. Rz. 20 f.; Pierre Moor/Alexandre Flückiger/Vincent Martenet, Droit administratif, Bd. I, Bern 2012, S. 187 f. und S. 194 f.; vgl. auch BGE 118 Ia 510 E. 4c S. 513 und Urteil 1P. 539/2003 vom 22. April 2004 E. 2.3 und 2.7 zur Anwendbarkeit von neu erlassenen Planungszonen im Rechtsmittelverfahren).

7.4.3. Diese Grundsätze gelten jedoch nur, wenn nicht (wie hier) eine spezielle Übergangsbestimmung vorliegt. Diese ist für die rechtsanwendenden Behörden verbindlich, soweit sie nicht - generell oder im konkreten Anwendungsfall - mit übergeordnetem Recht und namentlich den Grundrechten unvereinbar ist.

7.4.4. Der Vertrauensschutz steht Rechtsänderungen nicht grundsätzlich entgegen und vermittelt keinen Anspruch auf Fortbestand der geltenden Rechtsordnung. Nach der Rechtsprechung kann es aber aus Gründen der Rechtsgleichheit, der Verhältnismässigkeit und des Willkürverbots sowie des Vertrauensschutzes verfassungsrechtlich geboten sein, eine angemessene Übergangsregelung zu schaffen, z.B. um zu verhindern, dass gutgläubig getätigte Investitionen nutzlos werden (BGE 134 I 23 E. 7.6.1 S. 40 f.; 130 I 26 E. 8.1 S. 60; 123 II 385 E. 9 S. 395 ff.; 117 II 452 E. 3a S. 455; je mit Hinweisen).
Nach Beatrice Weber-Dürler (Neuere Entwicklung des Vertrauensschutzes, in: ZBl 103/2002 S. 281 ff., insbes. S. 307 f.) ist stets abzuklären, ab wann der Private grundsätzlich mit einer Rechtsänderung rechnen musste. Alle nach diesem Zeitpunkt getroffenen Dispositionen seien unbeachtlich. Nur die vorher in berechtigtem Vertrauen getroffenen nachteiligen Dispositionen könnten allenfalls einen Anspruch auf eine angemessene Übergangslösung verschaffen. Allerdings sei dafür eine Interessenabwägung vorausgesetzt. Als adäquate Rechtsfolge komme neben der Übergangsfrist allenfalls auch eine Entschädigung in Betracht, wenn die sofortige Geltung des neuen Rechts zur Erreichung des angestrebten Ziels unabdingbar sei.

7.5. Art. 55 BauR-2013 sieht vor, dass das neue Reglement auf alle Baugesuche anwendbar ist, die noch nicht rechtskräftig bewilligt worden sind. Dies gilt für sämtliche Bauvorschriften, unabhängig vom Gewicht der öffentlichen Interessen an ihrer Durchsetzung und der entgegenstehenden privaten Interessen. Es erscheint deshalb fraglich, ob diese Bestimmung den Grundsätzen der Rechtssicherheit und des Vertrauensschutzes in allen Fällen genügend Rechnung trägt. Wie der vorliegende Sachverhalt zeigt, kann es von Zufälligkeiten abhängen, ob die Baubewilligung noch vor Inkrafttreten der neuen Bestimmungen rechtskräftig wird oder nicht. Zudem kann für die Nachbarn ein Anreiz geschaffen werden, das Verfahren mit Rechtsmitteln zu verzögern.
Die Beschwerdeführer stellen allerdings die Verfassungsmässigkeit der kommunalen Übergangsbestimmung nicht generell in Frage; sie sind sogar selber der Auffassung, dass das neue Recht vom Departement im Verwaltungsbeschwerdeverfahren hätte angewendet werden müssen, wenn es zum damaligen Zeitpunkt bereits in Kraft gewesen wäre. Sie rügen einzig eine Verletzung von Treu und Glauben und des Vertrauensschutzes aufgrund der konkreten Umstände des vorliegenden Falls. Wie bereits dargelegt wurde (oben E. 7.3), liegt keine Zusicherung der Gemeinde vor. Auch die übrigen Umstände des Falles begründen kein schutzwürdiges Vertrauen der Beschwerdeführer in die Weitergeltung der alten Bauvorschriften:
Die Revision der Ortsplanung von Walzenhausen wurde schon seit Anfang 2007 angekündigt und hierfür am 3. Januar 2007 eine Planungszone erlassen. Am 25. Mai 2009 - und damit noch vor der öffentlichen Auflage des Baugesuchs - begann das öffentliche Mitwirkungsverfahren ("Volksdiskussion") für die revidierte Ortsplanung. Diese hatte insbesondere zum Ziel, die kommunalen Bauvorschriften an das neue Baurecht des Kantons anzupassen; in diesem Zusammenhang sollten erstmals auch Ausnützungsvorschriften eingeführt werden. Der Widerspruch des Baugesuchs zu den geplanten Ausnützungsvorschriften für die W1 wurde deshalb von Anfang an in den Einsprachen thematisiert.
Angesichts der schon damals geltenden Übergangsbestimmung (Art. 55 BauR-1996/97) mussten die sachkundigen Beschwerdeführer schon bei Einreichung des Baugesuchs 2009, jedenfalls aber bei dessen öffentlicher Auflage 2010, damit rechnen, dass die neuen Ausnützungsbestimmungen auf ihr Baugesuch Anwendung finden könnten, wenn die Ortsplanungsrevision vor Rechtskraft der Baubewilligung in Kraft treten sollte. Dies war aufgrund der zu erwartenden öffentlich- und zivilrechtlichen Einsprachen gegen das Baugesuch nicht unwahrscheinlich. Die Beschwerdeführer hätten die geplante Ausnützung reduzieren können, um das Risiko einer Baugesuchsabweisung abzuwenden. Wenn sie statt dessen eine möglichst rasche Behandlung anstrebten, um noch von den grosszügigeren Regeln des alten Rechts zu profitieren, durften sie doch nicht darauf vertrauen, dass ihr Baugesuch noch nach altem Recht beurteilt würde, sondern nahmen das Risiko einer Rechtsänderung bewusst in Kauf.

8. Die Beschwerdeführer machen eventualiter geltend, die Aufhebung der Baubewilligung sei unverhältnismässig gewesen und verletze die Eigentumsgarantie (Art. 26
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 26 Eigentumsgarantie - 1 Das Eigentum ist gewährleistet.
1    Das Eigentum ist gewährleistet.
2    Enteignungen und Eigentumsbeschränkungen, die einer Enteignung gleichkommen, werden voll entschädigt.
BV).

8.1. Sie sind der Auffassung, dass es zur Einhaltung der nach Art. 18 BauR-2013 gebotenen Ausnützung genügen würde, die Nutzung von bestimmten Räumen abzuändern, allenfalls verbunden mit minimalen Änderungen an die Ausgestaltung (Reduktion der Belichtung). Es sei daher unverhältnismässig, die ansonsten regelkonforme Baubewilligung vollständig aufzuheben. Vielmehr hätte eine Auflage gemäss Art. 106 Abs. 1 BauG/AR verfügt werden müssen, mit der Verpflichtung, vor Baubeginn Korrekturpläne zum Nachweis der Einhaltung von Art. 18 BauR-2013 einzureichen und diese den Beschwerdegegnern vor der Genehmigung durch die Baubehörde zur Stellungnahme zuzustellen.
Diese Vorgehensweise sei auch deshalb geboten, weil nach Art. 56 BauG/AR eingezontes, noch unüberbautes Land innert 10 Jahren ab Inkrafttreten des Gesetzes zu überbauen sei, ansonsten es ohne Entschädigungsfolgen als ausgezont gelte. Die Baukommission Walzenhausen habe ihnen am 28. Oktober 2013 mitgeteilt, dass die Bauparzelle per 1. Januar 2014 als Nichtbaugebiet zu betrachten sei. Zwar habe die Gemeinde zwischenzeitlich beim DBU ein Gesuch um Fristverlängerung nach Art. 56 Abs. 1 Satz 3 BauG/AR eingereicht; darüber sei aber noch nicht entschieden worden.

8.2. Die Beschwerdegegner bestreiten, dass eine Auflage genügt hätte: Die Abweichung von der Ausnützungsziffer sei alles andere als geringfügig; ihres Erachtens müsse das Bauvorhaben um ein ganzes Stockwerk reduziert werden. Es stehe auch noch nicht fest, dass das Bauvorhaben im Übrigen (von der Ausnützung abgesehen) baurechtskonform sei: Das Obergericht habe die Frage, ob die Zufahrt ausreichend sei, nicht abschliessend geprüft.
Die Vorbringen zu Art. 56 BauG/AR seien als echte Noven unzulässig. Im Übrigen habe der Regierungsrat zwischenzeitlich den Vollzug dieser Bestimmung ausgesetzt, weil die dort statuierten Überbauungsfristen bundesrechtswidrig seien.

8.3. Es erübrigt sich, auf die Einwände der Beschwerdegegner näher einzugehen. Die Beschwerdeführer tun nämlich nicht dar, inwiefern das von ihnen befürwortete Vorgehen wesentlich schneller oder einfacher oder aus anderen Gründen klar vorzugswürdig wäre. Sie räumen selbst ein, dass eine ergänzende Planung nötig wäre und diese den Beschwerdegegnern zur Stellungnahme zugesandt und anschliessend von der Gemeinde genehmigt werden müsste. Gegen diesen Entscheid wären wiederum Rechtsmittel zulässig. Der einzige Zeitgewinn ergäbe sich daher (möglicherweise) aus dem Verzicht auf eine erneute öffentliche Ausschreibung des Projekts. Dieser Zeitgewinn erscheint nicht so gewichtig, dass er die Anordnung einer Auflage unter dem Blickwinkel des Verhältnismässigkeitsprinzips zwingend gebieten würde.

8.4. Daran ändert auch der Hinweis auf Art. 56 BauG/AR nichts: Das darin genannte Datum betrifft den Beginn der Bauarbeiten (Abs. 3) und nicht die Erteilung der Baubewilligung. Es ist nicht erstellt, dass die Beschwerdeführer, selbst im Fall der Anordnung einer Auflage, vor dem 1. Januar 2014 mit den Bauarbeiten hätten beginnen können. Weitere Erwägungen zu dieser Frage erübrigen sich jedoch: Sofern Art. 56 BauG überhaupt noch zur Anwendung gelangen sollte, wird den Beschwerdeführern Gelegenheit zu geben sein, zu den besonderen Umständen Stellung zu nehmen, die es ihnen verunmöglicht haben, die schon lange geplante Überbauung ihres Grundstücks zu realisieren.

9.
Schliesslich beanstanden die Beschwerdeführer die obergerichtliche Kostenregelung.

9.1. In erster Linie machen sie geltend, dass es willkürlich sei, ihnen die gesamten gerichtlichen und aussergerichtlichen Kosten der Beschwerde- und Rekursverfahren aufzuerlegen: Der Umstand, dass sie nur aufgrund der kurz vor Entscheidfällung in Kraft getretenen neuen Bauvorschriften unterlegen seien, hätte zu ihren Gunsten berücksichtigt werden müssen, in sachgemässer Anwendung von Art. 19 Abs. 4 VRPG/AR bzw. Art. 22 Abs. 4 VRPG/AR. Statt dessen habe das Obergericht in E. 6.1 (S. 16) des Urteils II 10 45 (1C 25/2014) tatsachen- und entscheidwidrig festgehalten: "Billigkeitsgründe für eine abweichende Verlegung seien weder dargetan noch ersichtlich".
Art. 53 Abs. 1 VRPG/AR verweist auf die allgemeine Kostenregelung in Art. 19 ff. VRPG/AR; nach Abs. 3 hat die obsiegende Partei in der Regel Anspruch auf eine Entschädigung für ihre notwendigen Kosten und Auslagen.
Art. 19 Abs. 3 VRPG/AR enthält die Grundregel, wonach im Rechtsmittelverfahren gebühren- und kostenpflichtig ist, wer ganz oder teilweise unterliegt oder auf dessen Rechtsmittel nicht eingetreten wird. Abs. 4 sieht vor, dass der obsiegenden Partei Gebühren und Kosten ganz oder teilweise auferlegt werden können, wenn sie die Voraussetzungen des Obsiegens erst im Rechtsmittelverfahren geschaffen hat. In diesem Fall wird ihr nach Art. 24 Abs. 3 lit. b VRPG/AR auch keine Parteientschädigung ausgerichtet. Schliesslich bestimmt Art. 22 Abs. 4 VRPG/AR, dass bei Amtshandlungen, die mit geringem Aufwand verbunden sind, bei Nichteintretens- und Abschreibungsbeschlüssen sowie aus Gründen der Billigkeit von der Erhebung von Verfahrenskosten ganz oder teilweise abgesehen werden kann.
Art. 19 Abs. 4 VRPG/AR verlangt, dass die Voraussetzung für das Obsiegen im Rechtsmittelverfahren von der obsiegenden Partei "geschaffen" wurde; dies ist nicht der Fall bei einer Rechtsänderung, die ohne Zutun der Parteien in Kraft tritt. Art. 22 Abs. 4 VRPG/AR ("Gründe der Billigkeit") erlaubt nur den Verzicht auf die Kostenerhebung, nicht aber die Kostenverlegung zu Lasten der obsiegenden Partei. Immerhin aber zeigen diese Bestimmungen, dass die Kostenverteilung nach dem Unterliegerprinzip keine starre Regel ist, sondern dass Ausnahmen im Einzelfall möglich und geboten sein können.

9.1.1. Im Verfahren vor Obergericht erhielten die Beschwerdeführer Gelegenheit, zum neu in Kraft getretenen Baureglement der Gemeinde Stellung zu nehmen und ihre Anträge an die neue Rechtslage anzupassen. Von dieser Möglichkeit machten sie keinen Gebrauch, sondern beschränkten sich darauf, die Anwendbarkeit der neuen Bauvorschriften auf ihr Bauvorhaben zu bestreiten. Unter diesen Umständen erscheint es zumindest nicht willkürlich, ihnen die Verfahrens- und Parteikosten vor Obergericht vollständig aufzuerlegen.

9.1.2. Gleiches gilt jedoch nicht für die Rekursverfahren, mussten doch die Rekurse vom DBU nach dem zum Entscheidzeitpunkt geltenden Recht abgewiesen werden. Das Obergericht hat sich mit dieser Frage nicht auseinandergesetzt, obwohl es insoweit über volle Überprüfungsbefugnis verfügte, d.h. eigene Ermessens- und Billigkeitserwägungen anstellen konnte (Art. 56 Abs. 3 i.V.m. Art. 19 und Art. 24 VRPG/AR). Es ist daher nicht ersichtlich, ob es seinen Ermessensspielraum ausgeschöpft hat; jedenfalls aber fehlt eine genügende Begründung in diesem Punkt (Art. 29 Abs. 2
SR 101 Bundesverfassung der Schweizerischen Eidgenossenschaft vom 18. April 1999
BV Art. 29 Allgemeine Verfahrensgarantien - 1 Jede Person hat in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf gleiche und gerechte Behandlung sowie auf Beurteilung innert angemessener Frist.
1    Jede Person hat in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf gleiche und gerechte Behandlung sowie auf Beurteilung innert angemessener Frist.
2    Die Parteien haben Anspruch auf rechtliches Gehör.
3    Jede Person, die nicht über die erforderlichen Mittel verfügt, hat Anspruch auf unentgeltliche Rechtspflege, wenn ihr Rechtsbegehren nicht aussichtslos erscheint. Soweit es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand.
BV). Dies führt zur Rückweisung der Sache zu neuer Beurteilung der Verfahrens- und Parteikosten für die Rekursverfahren.

9.2. Begründet ist auch die Rüge der Beschwerdeführer, wonach der Kostenentscheid des DBU für diejenigen Einsprecher rechtskräftig geworden ist, die den Rekursentscheid nicht ans Obergericht weitergezogen haben. Dies betrifft zum einen die Rekurrenten I. und J. K.________, die nicht Beschwerde ans Obergericht geführt haben, zum anderen D.________, der seine Beschwerde vor Obergericht zurückgezogen hat. Diese Rekurrenten haben den Kostenentscheid des DBU akzeptiert, weshalb der auf sie entfallende Anteil der Staatsgebühr und der Parteientschädigung vom Obergericht nicht neu zu verlegen war.

9.3. Soweit die Beschwerdeführer dagegen rügen, dass es willkürlich sei, dem Beschwerdegegner 2 für das Rekursverfahren eine Parteientschädigung zuzusprechen, obwohl er in jenem Verfahren nicht anwaltlich vertreten gewesen sei, fehlt es an einer genügenden Beschwerdebegründung: Es wird weder dargelegt, aus welchen Verfahrensbestimmungen oder Grundsätzen des kantonalen Rechts sich ergibt, dass nur anwaltlich vertretene Parteien Anspruch auf eine Parteientschädigung (in der Höhe von Fr. 2'000.--) haben, noch inwiefern diese Regeln willkürlich angewendet wurden. Auf diese Rüge ist daher vorliegend nicht einzutreten (Art. 106 Abs. 2
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 106 Rechtsanwendung - 1 Das Bundesgericht wendet das Recht von Amtes wegen an.
1    Das Bundesgericht wendet das Recht von Amtes wegen an.
2    Es prüft die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist.
BGG).

10.
Nach dem Gesagten ist die Beschwerde teilweise, hinsichtlich der Kosten der Rekursverfahren, gutzuheissen und im Übrigen abzuweisen, soweit darauf einzutreten ist.
Bei diesem Ausgang des Verfahrens unterliegen die Beschwerdeführer im Wesentlichen. Sie werden daher im bundesgerichtlichen Verfahren kosten- und entschädigungspflichtig (Art. 66
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 66 Erhebung und Verteilung der Gerichtskosten - 1 Die Gerichtskosten werden in der Regel der unterliegenden Partei auferlegt. Wenn die Umstände es rechtfertigen, kann das Bundesgericht die Kosten anders verteilen oder darauf verzichten, Kosten zu erheben.
1    Die Gerichtskosten werden in der Regel der unterliegenden Partei auferlegt. Wenn die Umstände es rechtfertigen, kann das Bundesgericht die Kosten anders verteilen oder darauf verzichten, Kosten zu erheben.
2    Wird ein Fall durch Abstandserklärung oder Vergleich erledigt, so kann auf die Erhebung von Gerichtskosten ganz oder teilweise verzichtet werden.
3    Unnötige Kosten hat zu bezahlen, wer sie verursacht.
4    Dem Bund, den Kantonen und den Gemeinden sowie mit öffentlich-rechtlichen Aufgaben betrauten Organisationen dürfen in der Regel keine Gerichtskosten auferlegt werden, wenn sie in ihrem amtlichen Wirkungskreis, ohne dass es sich um ihr Vermögensinteresse handelt, das Bundesgericht in Anspruch nehmen oder wenn gegen ihre Entscheide in solchen Angelegenheiten Beschwerde geführt worden ist.
5    Mehrere Personen haben die ihnen gemeinsam auferlegten Gerichtskosten, wenn nichts anderes bestimmt ist, zu gleichen Teilen und unter solidarischer Haftung zu tragen.
und 68
SR 173.110 Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (Bundesgerichtsgesetz, BGG) - Bundesgerichtsgesetz
BGG Art. 68 Parteientschädigung - 1 Das Bundesgericht bestimmt im Urteil, ob und in welchem Mass die Kosten der obsiegenden Partei von der unterliegenden zu ersetzen sind.
1    Das Bundesgericht bestimmt im Urteil, ob und in welchem Mass die Kosten der obsiegenden Partei von der unterliegenden zu ersetzen sind.
2    Die unterliegende Partei wird in der Regel verpflichtet, der obsiegenden Partei nach Massgabe des Tarifs des Bundesgerichts alle durch den Rechtsstreit verursachten notwendigen Kosten zu ersetzen.
3    Bund, Kantonen und Gemeinden sowie mit öffentlich-rechtlichen Aufgaben betrauten Organisationen wird in der Regel keine Parteientschädigung zugesprochen, wenn sie in ihrem amtlichen Wirkungskreis obsiegen.
4    Artikel 66 Absätze 3 und 5 ist sinngemäss anwendbar.
5    Der Entscheid der Vorinstanz über die Parteientschädigung wird vom Bundesgericht je nach Ausgang des Verfahrens bestätigt, aufgehoben oder geändert. Dabei kann das Gericht die Entschädigung nach Massgabe des anwendbaren eidgenössischen oder kantonalen Tarifs selbst festsetzen oder die Festsetzung der Vorinstanz übertragen.
BGG). Ihrem Obsiegen in einem Nebenpunkt ist bei der Bemessung der Gerichtskosten und der Parteientschädigung Rechnung zu tragen.

Demnach erkennt das Bundesgericht:

1.
Die Verfahren 1C 23/2014 und 1C 25/2014 werden vereinigt.

2.
In teilweiser Gutheissung der Beschwerden werden Disp.-Ziff. 5, 6 und 7 (letztere soweit die Parteientschädigung der Beschwerdeführer betreffend) des Urteils II 10 43 und Disp.-Ziff. 4 und 5 des Urteils II 10 45 des Obergerichts Appenzell Ausserrhoden, 4. Abteilung, vom 24. April 2013, aufgehoben und die Sache zur Neuverlegung der Kosten und Entschädigungen der Rekursverfahren zurückgewiesen. Im Übrigen werden die Beschwerden abgewiesen, soweit darauf einzutreten ist.

3.
Die Gerichtskosten von Fr. 3'500.-- werden den Beschwerdeführern auferlegt.

4.
Die Beschwerdeführer haben C.________, E.________ und F.________ (Beschwerdegegner 1) mit insgesamt Fr. 3'500.-- und G.________ (Beschwerdegegner 2) für das bundesgerichtliche Verfahren mit Fr. 3'500.-- zu entschädigen.

5.
Dieses Urteil wird den Parteien, der Baubewilligungskommission Walzenhausen, dem Departement Bau und Umwelt und dem Obergericht Appenzell Ausserrhoden, 4. Abteilung, schriftlich mitgeteilt.

Lausanne, 24. März 2015

Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts

Das präsidierende Mitglied: Merkli

Die Gerichtsschreiberin: Gerber