Sehr geehrte Fragestellerin,
gerne beantworte ich Ihre Fragen wie folgt:
Zunächst einmal ist festzustellen, dass es in Baden-Württemberg keine (innerörtliche) Einfriedungspflicht gibt, das bedeutet, dass Sie sich mit Ihrem Nachbarn damals (1996) über eine Einfriedung in Form der (von Ihnen gesetzten) Bepflanzung geeinigt haben.
Wenn aber der Nachbar einverstanden war und eine lebende Einfriedung auf die Grundstücksgrenze gesetzt werden durfte, dann führt das dazu, dass die Ziersträucher rechtlich gesehen zur Grenzanlage geworden sind.
Daraus folgt gem. § 921, dass keiner der beiden Nachbarn allein über die Befriedung verfügen darf:
https://dejure.org/gesetze/BGB/921.html
Und es folgt daraus, dass die Einfriedung nicht ohne Ihre Zustimmung beseitigt werden darf, solange Sie an dem Fortbestand der Einrichtung ein Interesse haben, § 922 S. 3 BGB:
https://dejure.org/gesetze/BGB/922.html
Ich gehe deshalb davon aus, dass Ihr Nachbar nicht einfach Ihre Ziersträucher beseitigen darf, um jetzt eine neue Einfriedung herzustellen. Er ist dazu verpflichtet, mit Ihnen eine Einigung herzustellen. Weisen Sie Ihren Nachbarn auf die Möglichkeit einer einvernehmlichen Lösung hin, wie es das Nachbarrecht BW vorsieht, siehe hier:
https://www.service-bw.de/lebenslage/-/sbw/Nachbarschaft-5001078-lebenslage-0
Zu Ihren Fragen im einzelnen:
"a) Ist ein Doppelstabzaun, der vollständig blickdicht mit Plastik durchflochten ist, noch ein Drahtzaun oder muss der Nachbar diesen 1,80 m hohen Zaun um 30 cm nach innen versetzen?"
Nein, ein vollständig blickdichter Zaun, wie Sie ihn beschreiben, ist kein Drahtzaun mehr im Sinne des Gesetzes. Die Idee des Gesetzgebers geht ja dahin, die Einfriedung (blick)durchlässig zu halten, um die Beeinträchtigung des Nachbarn möglichst gering zu halten, die durch eine Einfriedung entstehen kann. Ein vollständig blickdichter Zaun entspricht diese Idee gerade nicht. Es gilt also meiner Ansicht nach auf jeden Fall § 10 Abs 2 NRG BW.
"b) Haben wir auf Basis der 25 Jahre alten Absprache einen Anspruch darauf, dass unsere Ziersträucher stehen bleiben dürfen?"
Ich meine: Ja. Zum einen gilt § 26 Abs. 1 S 1 NRG BW: 5jährige Verjährung. Zum anderen sind diese Ziersträucher meiner Ansicht nach eine Einfriedung im Sinne der §§ 921, 922 BGB geworden mit den entsprechenden günstigen rechtlichen Konsequenzen für Sie.
Fazit: Wenn Sie idealerweise die seinerzeitige Einigung mit dem Nachbarn belegen können, z. B. durch einen Zeugen, dann gilt hier ganz klar zu Ihren Gunsten die damalige Einigung auf eine Einfriedung zwischen den Grundstücken in Form der von ihnen gepflanzten Ziersträucher. Daran muss sich der Nachbar auch aus dem im Nachbarschaftsrecht geltenden Grundsatz "Treu und Glauben" (§ 242 BGB) halten, siehe etwa hier:
https://www.jusmeum.de/urteil/lg_freiburg/lg_freiburg_3-S-143-14
Ihr Recht auf Erhalt der Zierpflanzen als Einfriedung ergibt sich im übrigen aus §§ 921, 922 BGB.
Dass Ihr Nachbar Ihre Ziersträucher nicht einfach entfernen darf, folgt auch aus Gründen der insoweit geltenden Verjährung gemäß § 26 Abs. 1 S. 1 NRG BW.
Darüber hinaus müsste der vom Nachbarn geplante Zaun, wenn Sie denn damit einverstanden wären, den entsprechenden Abstand zu Ihrer Grundstücksgrenze einhalten.
Ich empfehle Ihnen, den Nachbarn auf die Rechtslage hinzuweisen. Wenn er sich uneinsichtig zeigt, sollten Sie sich - wenn vorhanden - an das gemeindliche Schiedsamt wenden.
Wenn noch etwas unklar geblieben oder nicht ausreichend erörtert worden ist, so fragen Sie gerne nach. Vorerst verbleibe ich mit freundlichen Grüßen und wünsche Ihnen alles Gute!
Elisabeth v. Dorrien
Rechtsanwältin