Sachverhalt: A. Mit Verfügungen des damaligen kantonalen Baudepartements (heute: Bau- und Justizdepartement) vom 4. März 1987 und der Baukommission Matzendorf vom 23. März 1987 wurde der Umbau des Schützenhauses Matzendorf bewilligt (Anbau und Sanierung sowie Schaffung von Parkplätzen). Das Baudepartement ordnete - als Auflage zur Ausnahmebewilligung nach Art. 24 RPG (SR 700) - explizit die Erstellung einer in den Bauplänen vorgesehenen Lärmschutzwand an. Diese ist bis heute nicht errichtet worden. B. Am 22. Februar 2007 publizierte die Baukommission der Gemeinde Matzendorf ein Baugesuch für die Erneuerung der Nummerierung ihres zum Schiessstand gehörenden Scheibenstands. Die Eheleute X._ erhoben als von einer Überschreitung des Immissionsgrenzwerts betroffene Anwohner während der Auflagefrist Einsprache gegen das Bauvorhaben. Sie beantragten die Rückweisung des Baugesuchs an die Gemeinde zur Vervollständigung und Verbesserung sowie eventualiter die Abweisung des Baugesuchs. Zudem verlangten sie in einer ergänzenden Eingabe vom 29. März 2007 den teilweisen Widerruf früherer Bewilligungen der kantonalen und kommunalen Behörden, wie sie der heutigen Schiessanlage und deren Betrieb zugrunde liegen. Insbesondere beantragten sie: "2.1 Die Verfügungen des Bau- und Justizdepartementes vom 4. März 1987 so- wie diejenige der Baukommission Matzendorf vom 23. März 1987 seien in- soweit teilweise zu widerrufen, als mit ihnen ein Schiessbetrieb mit einem maximalen Äquivalent von jährlich 15'000 Schüssen und 25 gewichteten Schiesshalbtagen bewilligt bzw. Sanierungserleichterungen gewährt wurden, und es sei der Betrieb der Schiessanlage auf das lärmschutzrechtlich zuläs- sige Mass zu reduzieren bzw. innert angemessener Frist einzustellen. 2.2 Eventualiter sei der Schiessbetrieb auf die vom Bund unterstützten Schiess- anlässe zu reduzieren, und es sei die Gesuchstellerin zu verpflichten, die gemäss Verfügung vom 4. März 1987 auferlegte Lärmschutzwand umgehend zu erstellen, verbunden mit der Androhung, dass im UnterlassungsfaIl ein Vollstreckungsverfahren beim zuständigen Oberamtmann eingeleitet werde. 2.3 Subeventualiter sei der Schiessbetrieb auf das mit Verfügung des Bau- und Justizdepartements vom 4. März 1987 bzw. 10. Mai 2004 definierte Mass zu reduzieren und die Gesuchstellerin zu verpflichten, die gemäss Verfü- gung vom 4. März 1987 auferlegte Lärmschutzwand umgehend zu erstel- len, verbunden mit der Androhung, dass im Unterlassungsfall ein Vollstre- ckungsverfahren beim zuständigen Oberamtmann eingeleitet werde." Mit Verfügungen vom 25. September 2008 schrieb das Bau- und Justizdepartement die Einsprache gegen die Erneuerung der Nummerierung als gegenstandslos geworden ab und trat auf die Begehren 2.1 bis 2.3 zur Behebung des rechtswidrigen Zustands nicht ein. Den Entscheid, auf die Begehren 2.1 bis 2.3 nicht einzutreten, begründete das Bau- und Justizdepartement mit der fehlenden Parteistellung der Eheleute X._, weil ihnen lediglich die Rechtsstellung von Anzeigern zukomme. Gleichzeitig widerrief das Departement die Ausnahmebewilligung vom 4. März 1987 insofern teilweise, als die einzuhaltende Pegelkorrektur verschärft wurde. Ausserdem stellte es ein Vollstreckungsgesuch wegen der nicht erstellten, aber bereits 1987 verlangten Lärmschutzwand in Aussicht. Gegen die Verfügungen des Departements vom 25. September 2008 gelangten die Eheleute X._ an das Verwaltungsgericht des Kantons Solothurn, welches die Beschwerde mit Urteil vom 2. März 2009 abwies, soweit es darauf eintreten konnte. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. April 2009 beantragen die Eheleute X._ im Wesentlichen die Aufhebung des Urteils des Verwaltungsgerichts vom 2. März 2009 und der zugrunde liegenden kantonalen und kommunalen Entscheide sowie die Rückweisung der Sache an das Bau- und Justizdepartement zur materiellen Beurteilung ihrer Begehren. Eventualiter sei die Sache an das Verwaltungsgericht zurückzuweisen und subeventualiter solle das Bundesgericht den Betrieb der Schiessanlage auf das lärmschutzrechtlich zulässige Mass reduzieren. D. Das kantonale Bau- und Justizdepartement beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. Die Gemeinde Matzendorf und die örtliche Schiessplatzkommission liessen sich nicht vernehmen. Das Bundesamt für Umwelt (BAFU) kommt zum Schluss, dass die Anzahl der bewilligten Schiesshalbtage erheblich von den Richtwerten der eidgenössischen Schiessverordnung vom 5. Dezember 2003 (SR 512.31) abweiche. Es hält eine Begrenzung auf die in der Schiessverordnung erwähnten maximal sieben Schiesshalbtage für die Vereinstrainings und die Schiesswettkämpfe als angemessen. Das Verwaltungsgericht verzichtet auf eine Stellungnahme zu den Ausführungen des BAFU. Das Bau- und Justizdepartement und die Beschwerdeführer halten an ihren Standpunkten fest.