Sachverhalt: A. A.a Die einfache Gesellschaft X._, Früchte und Gemüse, Landquart, bewirtschaftet unter anderem eine Fläche von rund 32 Hektaren, worauf Erdbeeren, Zwetschgen und Himbeeren angebaut werden. Am 3. April 2006 reichten die Gesellschafter beim Amt für Jagd und Fischerei des Kantons Graubünden (nachfolgend: kantonales Amt) eine Wildschadensmeldung ein, die mit einem Gesuch um Vergütung eines im Winter 2005/2006 erlittenen und durch den Abfrass von Erdbeerkulturen durch Rotwild (Hirsche) verursachten Schadens verbunden war. Der daraufhin vom kantonalen Amt angeordnete Augenschein vom 6. April 2006 ergab, dass der vorhandene Zaun das Wild nicht von den Erdbeerkulturen fernzuhalten vermocht hatte. Am 9. Mai 2006 wies das kantonale Amt die Schadenforderung ab. Beschwerden beim Bau-, Verkehrs- und Forstdepartement Graubünden (nachfolgend: Departement) und beim Verwaltungsgericht des Kantons Graubünden (im Folgenden: Verwaltungsgericht) blieben erfolglos. A.b Mit Urteil 2C_562/2008 vom 28. Januar 2009 hiess das Bundesgericht eine bei ihm eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten teilweise gut, hob das Urteil des Verwaltungsgerichts vom 1. April 2008 auf, soweit es sich auf die Vergütung von Wildschäden im Gebiet "R._" bezog, und wies die Sache insofern an das Verwaltungsgericht zurück zu neuem Entscheid im Sinne der Erwägungen. Im Übrigen wies das Bundesgericht die Beschwerde ab. Das Bundesgericht führte dazu aus, die Begründung des verwaltungsgerichtlichen Urteils beziehe sich einzig auf die zwei Anbauflächen im Gebiet "S._". Zur dritten Anbaufläche im Gebiet "R._" und zu deren tatsächlichen Ausgangslage äussere sich das Verwaltungsgericht nicht, wodurch es insoweit den Anspruch der Beschwerdeführer auf rechtliches Gehör verletzt habe. A.c In der Folge führte das Verwaltungsgericht einen Schriftenwechsel sowie einen Augenschein vor Ort durch, um über die geltend gemachte Vergütung für den Rotwildschaden an den Erdbeerkulturen im Gebiet "R._" nochmals zu entscheiden. Am 9. Juni 2009 wies das Verwaltungsgericht die entsprechende Beschwerde ab. Zur Begründung führte es im Wesentlichen aus, die fragliche Anbaufläche sei zwar nicht wildexponiert, aber dennoch offensichtlich ungenügend eingezäunt gewesen, weshalb ein Anspruch auf Wildschadenvergütung entfalle. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht stellen A._ und B._ die folgenden Anträge: "1. Das angefochtene Urteil des Verwaltungsgerichts des Kantons Graubünden vom 9. Juni 2009 ... sei aufzuheben und der Kanton Graubünden sei zu verpflichten, den Beschwerdeführern eine Wildschadenvergütung von CHF 142'945.-- nebst 5 % Zins seit 13. Juli 2006 zu bezahlen. 2. Eventualiter sei die Sache an die Vorinstanz bzw. an die erstinstanzliche Behörde zum neuen Entscheid zurückzuweisen. ..." Zur Begründung wird im Wesentlichen geltend gemacht, das Beweisverfahren sei mangelhaft gewesen und das Urteil teilweise ungenügend begründet. Überdies verletze es die bundesrechtliche Regelung der Wildschadenvergütung und sei willkürlich und rechtsungleich. C. Das Departement schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt deren Abweisung, soweit darauf einzutreten sei. Das Bundesamt für Umwelt teilt mit, dass der angefochtene Entscheid nach seiner Ansicht die Bundesgesetzgebung über die Jagd nicht verletze. 