3./ Dem Verfahrensausgang entsprechend sind die amtlichen Kosten des
Beschwerdeverfahrens den Beschwerdegegnern aufzuerlegen (Art. 95 Abs. 1 VRP).
Eine Entscheidgebühr von Fr. 3'000.-- ist angemessen (Ziff. 382 Gerichtskostentarif,
sGS 941.12).

Die amtlichen Kosten des Rekursverfahrens von Fr. 1'200.-- sind ebenfalls den
Beschwerdegegnern aufzuerlegen (Art. 95 Abs. 1 VRP).

Ausseramtliche Kosten sind nicht zu entschädigen. Die Beschwerdegegner sind
unterlegen (Art. 98bis VRP), und dem Beschwerdeführer steht als verfügende Behörde
kein Anspruch auf Kostenersatz zu.

Demnach hat das Verwaltungsgericht zu Recht erkannt: