Sachverhalt:
A.
A.a. Zwischen den Eigentümern der Parzellen im Grundbuch Walenstadt Nr. 2756, A._ und B._, und Nr. 1897, C._, besteht seit nunmehr bald 20 Jahren ein Nachbarschaftsstreit. Am 12. April 2012 hiess das Verwaltungsgericht des Kantons St. Gallen eine von C._ erhobene Beschwerde teilweise gut und traf verschiedene Feststellungen zur im Nachbarstreit zentralen Stützmauer der Ehegatten A._ und B._, insbesondere dass die Mauer mit einer Höhe von insgesamt 2.20 m nur unter der Voraussetzung bewilligt worden sei, dass ein Satz Steine mit einer Höhe von 70 bis 80 cm um rund 60 cm zurückversetzt werde; im Übrigen wurde die Beschwerde abgewiesen, soweit darauf einzutreten war. In der Begründung des Urteils hielt das Verwaltungsgericht unter anderem ausdrücklich fest, es werde Sache des Gemeinderates sein, über die Herstellung des rechtmässigen Zustands zu befinden. Mit Urteil 1C_272/2012 vom 22. Januar 2013 wies das Bundesgericht eine dagegen von A._ eingereichte Beschwerde ab. Am 7. Mai 2015 wies das Bundesgericht ein ebenfalls von A._ gestelltes Revisionsgesuch ab (Urteil 1F_10/ 2015). Am 11. Juni 2015 verzichtete der Gemeinderat Walenstadt auf die Anordnung von Wiederhestellungsmassnahmen; die oberste Steinreihe der Stützmauer auf der Parzelle Nr. 2756 müsse nicht auf der ganzen Länge entlang der Parzelle Nr. 1897 zurückversetzt sein, die Höhenabweichung läge im Toleranzbereich und lediglich einzelne Steine würden, wenn überhaupt, das Grundeigentum unterirdisch überragen.
A.b. Am 13. Juni 2016 hiess das Baudepartement des Kantons St. Gallen einen von C._ dagegen erhobenen Rekurs im Sinne der Erwägungen gut, hob die Verfügung des Gemeinderates auf und wies die Sache zur Ermittlung des rechtserheblichen Sachverhalts und zu neuer Entscheidung im Sinne der Erwägungen an den Gemeinderat zurück.
B.
B.a. Gegen diesen Entscheid des Baudepartements reichten A._ und B._ Beschwerde beim Verwaltungsgericht des Kantons St. Gallen ein mit dem Antrag, ihn aufzuheben.
B.b. C._ erhob gegen diesen Entscheid des Baudepartements ebenfalls Beschwerde mit dem Antrag, ihn insoweit aufzuheben, als bezüglich des Zauns auf der Stützmauer keine Korrektur zu treffen sei, die Nichteinhaltung des Grenzabstands sowie die Überschreitung der Grenze nicht zu korrigieren seien und die Gemeinde Walenstadt den rechtserheblichen Sachverhalt erneut festzustellen habe.
B.c. Mit Entscheid vom 26. September 2018 vereinigte das Verwaltungsgericht die Beschwerden und wies diejenige von A._ und B._ ab. Diejenige von C._ hiess es gut, soweit es darauf eintrat. Das Verwaltungsgericht hob den bei ihm angefochtenen Departementsentscheid teilweise auf und wies die Gemeinde Walenstadt ausdrücklich an, die Wiederherstellung des rechtmässigen Zustandes unter Androhung der Ersatzvornahme im Sinne der Erwägungen anzuordnen. Überdies auferlegte es die Verfahrenskosten A._ und B._ und verpflichtete sie, C._ eine Parteientschädigung zu bezahlen.
C.
C.a. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht beantragen A._ und B._, den Entscheid des Verwaltungsgerichts vom 26. September 2018 aufzuheben und die Sache an das Verwaltungsgericht, eventuell an die erste Instanz zurückzuweisen. Mit der Rückweisung sei die Anordnung zu verbinden, dass C._ für das Rekursverfahren vor dem Baudepartement und das Beschwerdeverfahren vor dem Verwaltungsgericht die Verfahrenskosten und eine angemessene Parteientschädigung zu ihren Gunsten auferlegt werde. A._ und B._ ersuchten überdies, ihrer Beschwerde in Bezug auf die Bezahlung der ihnen zu Gunsten von C._ vom Baudepartement und vom Verwaltungsgericht auferlegten Parteientschädigungen aufschiebende Wirkung zuzuerkennen.
C.b. C._ beantragt in seiner Vernehmlassung, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Baudepartement und das Verwaltungsgericht des Kantons St. Gallen schliessen ohne weitere Ausführungen auf Abweisung der Beschwerde. Die Gemeinde Walenstadt beantragt, einen Augenschein durchzuführen zur Klärung von Fragen im Zusammenhang mit der Stützmauer bzw. mit dem abgegrabenen Terrain.
C.c. Das Bundesgericht eröffnete zur Beschwerde von A._ und B._ das Verfahren 1C_572/2018.
D.
D.a. Auch C._ führt gegen den Entscheid des Verwaltungsgerichts vom 26. September 2018 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt im Wesentlichen, den Entscheid des Verwaltungsgerichts in verschiedenen Punkten abzuändern. So seien die sinngemässen Anordnungen, dass die strittige Stützmauer keinen Grenzabstand von 0.5 m einzuhalten habe und eine Höhe von 2.2 m aufweisen dürfe, zu korrigieren und es sei festzuhalten, dass die Wiederherstellung der Stützmauer dem heutigen Baureglement der Gemeinde Walenstadt zu entsprechen habe.
D.b. A._ und B._ beantragen, die Beschwerde abzuweisen und die beiden Verfahren zu vereinigen. Das Baudepartement und das Verwaltungsgericht beantragen, die Beschwerde abzuweisen. Die Gemeinde Walenstadt beantragt, einen Augenschein durchzuführen zur Klärung von Fragen im Zusammenhang mit der Stützmauer bzw. mit dem abgegrabenen Terrain. Mit Replik vom 15. Februar 2019 hält C._ im Wesentlichen an seinem Standpunkt fest. A._ und B._ verzichteten auf eine weitere Stellungnahme.
D.c. Das Bundesgericht eröffnete zur Beschwerde von C._ das Verfahren 1C_574/2018.
E.
Mit Verfügung vom 22. Januar 2019 vereinigte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts die Verfahren 1C_572/2018 und 1C_574/2018. Gleichzeitig wies er das Gesuch von A._ und B._ um aufschiebende Wirkung ab.

Erwägungen:
1.
1.1. Die beiden bundesgerichtlichen Verfahren 1C_572/2018 und 1C_574/2018 wurden mit Präsidialverfügung vom 22. Januar 2019 bereits vereinigt. Dies braucht daher im vorliegenden Urteil nicht mehr angeordnet zu werden.
1.2. Angefochten ist ein kantonal letztinstanzlicher Entscheid auf dem Gebiet des Raumplanungs- und Baurechts, wofür das Bundesgerichtsgesetz keinen Ausschlussgrund enthält. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (vgl. Art. 82 ff. und Art. 86 Abs. 1 lit. d BGG).
1.3. Nach <ref-law> ist die Beschwerde zulässig gegen Entscheide, die das Verfahren abschliessen. Rückweisungsentscheide sind grundsätzlich Zwischenentscheide. Soweit der unteren Instanz, an die ein Rechtsstreit zurückgewiesen wird, kein Entscheidungsspielraum mehr verbleibt, sind Rückweisungsentscheide jedoch anfechtbar (vgl. <ref-ruling> E. 1.2 S. 148 mit Hinweis). Das trifft hier zu, wo die Gemeinde verbindlich angewiesen wird, ohne verbleibenden Entscheidungsspielraum die Wiederherstellung des rechtmässigen Zustands anzuordnen.
1.4. Streitgegenstand bilden weder die Feststellungen des Verwaltungsgerichts in dessen Urteil vom 12. April 2012 noch die Frage der nachträglichen Bewilligung der Stützmauer im heutigen Zustand. Im Streit steht hier einzig noch die Wiederherstellung des rechtmässigen Zustands bei der Stützmauer.
1.5. Alle drei Beschwerdeführer in beiden bundesgerichtlichen Verfahren waren am vorinstanzlichen Verfahren beteiligt und sind als damalige Beschwerdeführer sowie Gegenparteien und in der Streitsache unmittelbar Betroffene zur Beschwerde legitimiert (vgl. <ref-law>).
1.6. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht unter Einschluss des Bundesverfassungsrechts sowie die offensichtlich unrichtige, d.h. willkürliche, Feststellung des Sachverhalts gerügt werden (Art. 95 lit. a und Art. 97 Abs. 1 BGG).
1.7. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft jedoch unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) nur die geltend gemachten Vorbringen, sofern rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.5 S. 144). Gemäss <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Der Beschwerdeführer muss sich wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzen. Rein appellatorische Kritik ohne Bezug zum angefochtenen Entscheid genügt nicht. Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht wird. Dies prüft das Bundesgericht grundsätzlich nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>; vgl. <ref-ruling> E. 1.4 S. 176; <ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 1.4 S. 254 f.).
2.
2.1. Beide Beschwerdeschriften äussern sich detailliert zur Sache. Weitgehend werden dabei die altbekannten Standpunkte der Parteien dargelegt. Die Rechtsschriften sind insofern appellatorischer Natur und die entsprechenden Argumente nicht zu hören.
2.2. In der Sache ist zudem festzuhalten, dass auf die mit dem Urteil des Bundesgerichts 1C_272/2012 vom 22. Januar 2013 und dem Revisionsentscheid 1F_10/2015 vom 7. Mai 2015 erledigten Tat- und Rechtsfragen nicht mehr zurückzukommen ist. Diese Urteile bzw. der damit geschützte Entscheid des Verwaltungsgerichts vom 12. April 2012 bilden die Grundlage für die hier strittige Frage der Wiederherstellung der fraglichen Stützmauer. Soweit die Beschwerdeführer direkt oder indirekt versuchen, damals rechtskräftig entschiedene Gesichtspunkte wieder aufzuwerfen, sind die Beschwerden von vornherein unzulässig.
2.3. Insgesamt sind die Beschwerden nur insoweit zulässig, wie darauf nachfolgend eingegangen wird. Im Übrigen ist darauf nicht einzutreten.
3.
Die Parteien stellen in beiden Verfahren verschiedentlich die tatsächlichen Feststellungen der Vorinstanz in Frage oder unterbreiten dem Bundesgericht eine eigene Darstellung des Sachverhalts. Dass die tatsächlichen Feststellungen des Verwaltungsgerichts, soweit hier für das Wiederherstellungsverfahren überhaupt von Belang, offensichtlich unrichtig wären, wird jedoch weder nachvollziehbar dargetan noch ist es ersichtlich. Es braucht auch keine ergänzenden Abklärungen durch das Bundesgericht. Daran ändert der Antrag der Gemeinde auf Durchführung eines Augenscheins nichts. Dieser wird im Wesentlichen damit begründet, dass die heutigen Gemeindevertreter noch nicht so lange im Amt seien, um die Umstände des Falles zu kennen. Ausgangspunkt des vorliegenden Wiederherstellungsverfahrens ist jedoch ein Entscheid des Gemeinderates vom 11. Juni 2015. Damit verzichtete dieser im Anschluss an die Aufforderung des Verwaltungsgerichts in dessen Urteil vom 12. April 2012, über die Wiederherstellung zu befinden, darauf, hinsichtlich der strittigen Stützmauer die Wiederherstellung des rechtmässigen Zustandes anzuordnen. Wenn nunmehr die Gemeinde vor Bundesgericht geltend macht, sie kenne die tatsächlichen Verhältnisse ohne bundesgerichtlichen Augenschein nicht ausreichend, überzeugt dies mit Blick auf diesen Entscheid, auf die langjährige Geschichte und auf die verschiedenen durchlaufenen Verfahren nicht. Die heutigen Gemeindevertreter haben sich die Kenntnisse ihrer Vorgänger anrechnen zu lassen bzw. sind selbst dafür verantwortlich, sich diese zu verschaffen.
4.
4.1. Im Verfahren 1C_572/2018 rügen die Beschwerdeführer zunächst, das Verwaltungsgericht missachte den Grundsatz der res iudicata, indem es in E. 9.3 auch die Wiederherstellung des rechtmässigen Zustands des auf der Stützmauer errichteten Zauns verlange. Der Grundsatz der materiellen Rechtskraft sei bundesrechtlicher Natur. Wieweit dies zutrifft, kann hier offenbleiben. Die Beschwerdeführer legen selbst dar, dass ihre Gegenpartei bereits im ersten Verfahren vor dem Verwaltungsgericht den Antrag auf Wiederherstellung des rechtmässigen Zustands ausdrücklich auch im Hinblick auf den Zaun gestellt hatte. Indem das Verwaltungsgericht in seinem Urteil vom 12. April 2012 explizit feststellte, dass die Mauer mit einer Höhe von insgesamt 2.20 m nur unter der Voraussetzung bewilligt worden ist, dass ein Satz Steine mit einer Höhe von 70 bis 80 cm rund 60 cm zurückversetzt werde, entschied es implizit auch über den Zaun. Da dieser auf der Mauer steht, ist eine Versetzung der obersten Steinschicht ohne Zaun faktisch gar nicht möglich. Überdies hatte der Gemeinderat damals ausdrücklich verfügt, der Zaun müsse nicht um 60 cm zurückversetzt werden. Nachdem das Verwaltungsgericht den diesen Gemeinderatsentscheid schützenden Rekursentscheid aufgehoben hatte, fiel nebst den übrigen kommunalen Anordnungen auch diese Verfügung dahin. Über die Pflicht zur Rückversetzung des Zauns wurde damit eindeutig mit entschieden. Demnach konnte das Verwaltungsgericht in seinem hier strittigen zweiten Urteil auch insoweit die Wiederherstellung anordnen.
4.2. Unzutreffend ist sodann der Standpunkt der Beschwerdeführer, das Verwaltungsgericht gehe zu Unrecht von einer Bindungswirkung seines ersten Urteils für die Behörden, die Gerichte und die Verfahrensbeteiligten aus. Das Verwaltungsgericht beschränkte sich damals zwar formell auf einen Feststellungsentscheid. Es hielt aber, wenn auch nicht im Dispositiv, so doch in der Begründung seines Urteils ausdrücklich fest, es werde Sache des Gemeinderates sein, über die Herstellung des rechtmässigen Zustands zu befinden. Dieses Urteil wurde vom Bundesgericht geschützt. Soweit das Verwaltungsgericht damals Feststellungen traf, entfalteten diese in der Folge uneingeschränkt verbindliche Rechtswirkung. Mit dem hier angefochtenen zweiten Urteil wies das Verwaltungsgericht die Gemeinde nunmehr explizit an, die Wiederherstellung des rechtmässigen Zustandes unter Androhung der Ersatzvornahme im Sinne der Erwägungen anzuordnen. Dabei ist das erste Urteil inhaltlich verbindlich und kann nicht mehr abgeändert werden. Worin hier eine Bundesrechtsverletzung liegen sollte, ist unerfindlich.
4.3. Schliesslich verstösst der angefochtene Entscheid auch insofern nicht gegen Bundesrecht, als er die Wiederherstellung des rechtmässigen Zustands als verhältnismässig beurteilt. Dabei geht es im Wesentlichen um die Rückversetzung der obersten Schicht Steine der Stützmauer zusammen mit dem darauf errichteten Zaun um 60 cm. Das Verwaltungsgericht begründet die Verhältnismässigkeit in E. 9.4 ff. des angefochtenen Urteils ausführlich. Dieses enthält dazu detaillierte und nachvollziehbare Angaben zu den tatsächlichen Verhältnissen und der Rechtslage. Der entsprechenden Abwägung ist nichts beizufügen. Die Beschwerdeführer rügen in diesem Zusammenhang auch eine Gehörsverweigerung, weil das Verwaltungsgericht ihren Beweisanträgen insbesondere zu den von der Gegenpartei in den Jahren 2000 und 2010 vorgenommenen Abgrabungen keine Folge geleistet habe. Die Vorinstanz durfte dies jedoch als unmassgeblich beurteilen. Die grundsätzliche Pflicht zur Rückversetzung der Mauer steht seit dem ersten vom Bundesgericht geschützten verwaltungsgerichtlichen Urteil fest, woran die älteren fraglichen Abgrabungen und deren Umstände nichts ändern. Sie erscheinen auch nicht entscheidwesentlich für die Frage der Verhältnismässigkeit der Anordnung der Wiederherstellung des rechtmässigen Zustands.
4.4. Die von den Beschwerdeführern im Verfahren 1C_572/2018 erhobenen Rügen erweisen sich demnach als unbegründet, soweit sie zu behandeln sind.
5.
5.1. Im Verfahren 1C_574/2918 rügt der Beschwerdeführer einen Verstoss gegen seine Eigentumsrechte nach <ref-law> und macht geltend, der angefochtene Entscheid sei willkürlich gemäss <ref-law> und rechtsungleich nach <ref-law>. Weiter verstosse er gegen Art. 22 Abs. 1 RPG. Überdies habe das Verwaltungsgericht seine Ansprüche auf ein faires Verfahren gemäss <ref-law> und Art. 6 Ziff. 1 EMRK sowie auf eine wirksame Beschwerde nach Art. 13 EMRK verletzt.
5.2. Art. 13 EMRK verschafft ein lediglich akzessorisches Beschwerderecht. Der Beschwerdeführer legt nicht dar, an welches Menschenrecht ein solches Beschwerderecht im vorliegenden Zusammenhang anknüpfen sollte. Nicht ausreichend ausgeführt wird sodann, inwiefern Art. 6 Ziff. 1 EMRK verletzt sein und weshalb Art. 13 EMRK, falls beide Bestimmungen überhaupt anwendbar wären, einen weitergehenden Schutz gewähren sollte. Auf die behaupteten Konventionsverstösse ist daher nicht einzugehen.
5.3. Wie bereits dargelegt, sind sodann die materiellrechtlichen Entscheidungen des ersten verwaltungsgerichtlichen Urteils sowie die tatsächlichen Feststellungen der Vorinstanz im angefochtenen Entscheid verbindlich (vgl. vorne E. 2.2 und 3). In E. 4.4 des bundesgerichtlichen Urteils 1C_272/2012 vom 22. Januar 2013 wird aus dem damaligen Projektbeschrieb vom 27. Oktober 1998 als Bestandteil der Baubewilligung zitiert, wonach unter anderem eine Steinblockmauer mit Hinterfüllung entlang der Grenze errichtet werde und der damalige Nachbar damit einverstanden sei. Wenn der Beschwerdeführer darin eine Verletzung seiner Rechte sieht, ist das längst rechtskräftig entschieden, weshalb darauf nicht zurückzukommen ist. Dadurch wird weder gegen die Eigentumsgarantie des Beschwerdeführers verstossen noch ist der angefochtene Entscheid deswegen willkürlich oder rechtsungleich. Genauso wenig ist die Mauer nach der heute geltenden Rechtslage so zu korrigieren, wie wenn sie neu erstellt würde, wie der Beschwerdeführer behauptet. Vielmehr gilt die mit dem Urteil des Verwaltungsgerichts vom 12. April 2012 festgestellte Rechtslage. Das ist weder willkürlich noch verstösst es gegen Art. 22 Abs. 1 RPG, wonach Bauten und Anlagen nur mit behördlicher Bewilligung errichtet oder geändert werden dürfen. Ein solches Bewilligungsverfahren fand damals statt, und darin wurde die Errichtung der Mauer auf der Grenze gestattet. Es verletzt Bundesrecht nicht, wenn die Vorinstanz darauf abstellte und nicht eine Rückversetzung der ganzen Mauer um 0.5 m und eine Maximalhöhe auf der ganzen Mauerlänge von 1.8 m anordnete. Nur wurden in der Folge die mit der erteilten Baubewilligung vorgegebenen Dimensionen der Mauer nicht eingehalten. Das hat das Verwaltungsgericht in seinem ersten Urteil festgestellt und mit seinem zweiten, hier angefochtenen Urteil eine entsprechende Korrektur durch Wiederherstellung des rechtmässigen Zustandes angeordnet. Dies ist nicht zu beanstanden. Nicht ersichtlich ist schliesslich, inwiefern die Baubewilligung nachträglich erloschen sein und in diesem Zusammenhang die Vorinstanz eine Gehörsverweigerung begangen haben sollte, wie der Beschwerdeführer auch noch geltend macht. Auch darauf wäre im vorliegenden Verfahren ohnehin nicht mehr zurückzukommen, da die entsprechende Rechtslage wie bereits mehrfach erwähnt mit dem Urteil des Verwaltungsgerichts vom 12. April 2012 verbindlich festgestellt worden ist.
5.4. Damit erweisen sich auch die vom Beschwerdeführer im Verfahren 1C_574/2018 erhobenen Rügen als unbegründet, soweit sie zu behandeln sind.
6.
Zusammenfassend kann festgehalten werden, dass es mit dem angefochtenen Entscheid im Ergebnis einzig darum geht, das erste vom Bundesgericht geschützte Urteil des Verwaltungsgerichts vom 12. April 2012 durch Wiederherstellung des gemäss den entsprechenden Feststellungen und Erwägungen umschriebenen rechtmässigen Zustands umzusetzen. Die Gemeinde wird sich daran zu halten haben. Ergänzende Abklärungen sind nicht erforderlich. Soweit die Parteien weiterhin auf eigenen abweichenden Standpunkten beharren, sind sie nicht zu hören.
7.
Die Beschwerden erweisen sich als unbegründet und sind abzuweisen, soweit darauf eingetreten werden kann.
Die Kosten sind den gleichermassen in je einem bundesgerichtlichen Verfahren obsiegenden und unterliegenden Beschwerdeführern je hälftig aufzuerlegen. Die Beschwerdeführer im Verfahren 1C_572/2018 haften für ihren Anteil solidarisch (vgl. Art. 65 und 66 BGG). Die Anwaltskosten sind wettzuschlagen, womit keine Parteientschädigungen zuzusprechen sind (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerden in den bundesgerichtlichen Verfahren 1C_572/2018 und 1C_574/2018 werden abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von insgesamt Fr. 8'000.-- werden je zur Hälfte, ausmachend Fr. 4'000.--, einerseits den Beschwerdeführern im Verfahren 1C_572/2018 gemeinsam und mit Solidarhaftung und andererseits dem Beschwerdeführer im Verfahren 1C_574/2018 auferlegt.
3.
Eine Parteientschädigung wird nicht zugesprochen.
4.
Dieses Urteil wird den Parteien, der Politischen Gemeinde Walenstadt, dem Baudepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 31. Oktober 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Uebersax