Die amtlichen Kosten des Rekursverfahrens von Fr. 1'200.-- sind dem
Verfahrensausgang entsprechend ebenfalls dem Staat aufzuerlegen (Art. 95 Abs. 1
VRP); auf ihre Erhebung ist zu verzichten (Art. 95 Abs. 3 VRP). Den Beschwerdeführern
ist der im Rekursverfahren geleistete Kostenvorschuss vollumfänglich
zurückzuerstatten.

Die Beschwerdeführer haben Anspruch auf eine ausseramtliche Entschädigung (Art.
98bis VRP). Ein Kostenersatz von Fr. 1'500.-- zuzügl. MWSt für das Rekurs- und
Beschwerdeverfahren ist angemessen.

Demnach hat das Verwaltungsgericht zu Recht erkannt:

1./ Die Beschwerde wird gutgeheissen.