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.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Endentscheid einer kantonalen Gerichtsbehörde (vgl. Art. 86 Abs. 1 lit. d in Verbindung mit <ref-law>), der eine Angelegenheit des öffentlichen Rechts betrifft und deshalb der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (<ref-law>). Weil zudem keiner der Ausschlussgründe gemäss <ref-law> vorliegt, erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich als zulässig. Die beiden Gesellschafter sind vom angefochtenen Urteil direkt betroffen und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Abänderung, weshalb ihnen die Beschwerdelegitimation nach <ref-law> zukommt.
1.2 Gemäss <ref-law> kann mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten insbesondere geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht - (lit. a) und Völkerrecht (lit. b). Das Bundesgericht überprüft die Verletzung kantonaler Bestimmungen, von hier nicht anwendbaren Ausnahmen abgesehen (vgl. Art. 95 lit. c-e BGG), nur insoweit, als eine derartige Rechtsverletzung einen Verstoss gegen Bundesrecht im Sinne von <ref-law>, insbesondere gegen das Willkürverbot (<ref-law>), oder Völkerrecht gemäss <ref-law> darstellt.
1.3 Grundsätzlich wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>). Nach <ref-law> ist jedoch in der Beschwerdeschrift in gedrängter Form darzulegen, inwiefern der angefochtene Akt gegen massgebliches Recht verstösst. Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht. Eine rein appellatorische Begründung genügt nicht (<ref-ruling> E. 3.1 S. 399). Vielmehr sind diese Rügen präzise vorzubringen und zu begründen (<ref-law>). Führt der Beschwerdeführer nicht zumindest in erkennbarer Weise an, welches Grundrecht seiner Meinung nach verletzt sei, und legt er nicht dar, worin die behauptete Verletzung bestehe, unterbleibt die Prüfung durch das Bundesgericht (<ref-ruling> E. 1.4.2 S. 254). Das gilt insbesondere für die Anrufung des Willkürverbots, wo die behauptete Unhaltbarkeit des Entscheides genau darzutun ist (<ref-ruling> E. 3.2 S. 400).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Von diesen tatsächlichen Feststellungen kann es nur dann abweichen, wenn sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>) und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2. 2.1 Die Beschwerdeführer rügen, sie hätten vor Verwaltungsgericht den zuständigen Chef-Wildhüter des Jagdbezirks 12 als Zeugen angerufen, wozu sich das Verwaltungsgericht nicht geäussert habe. Es habe den Wildhüter-Bezirkschef aber beim Augenschein beigezogen, dabei jedoch die anwendbaren Vorschriften über den Zeugenbeweis missachtet, womit die kantonal-rechtlichen Verfahrensgarantien verletzt worden seien. Darin liege auch ein Verstoss gegen <ref-law> und <ref-law>.
2.2 Wie sich aus den Akten ergibt, hatten die Beschwerdeführer im ersten Verfahren vor dem Verwaltungsgericht den Wildhüter-Bezirkschef als Zeugen angerufen. Die Vorinstanz wies den Antrag indessen in ihrem Urteil vom 1. April 2008 ab. Das fochten die Beschwerdeführer damals im ersten bundesgerichtlichen Verfahren 2C_562/2008, in dem die vorliegende Streitsache an das Verwaltungsgericht zurückgewiesen wurde, nicht an. Sie können darauf im vorliegenden Verfahren nicht mehr zurückkommen. Folgerichtig zog das Verwaltungsgericht den Chef-Wildhüter nunmehr nicht als Zeugen, sondern lediglich als Auskunftsperson zum Augenschein bei. Die entsprechenden Rügen der Beschwerdeführer über einen angeblichen Verstoss gegen die Vorschriften über den Zeugenbeweis stossen damit ins Leere.
3. 3.1 Die Beschwerdeführer machen wiederum geltend, der angefochtene Entscheid verletze ihren Anspruch auf eine genügende Begründung gemäss <ref-law>. Insbesondere wüssten sie nicht, warum gestützt auf dieselbe bundesrechtliche Rahmenvorschrift in einem Parallelfall im Kanton Aargau ohne jegliche Zäunung in unmittelbarer Waldnähe eine Wildschadenvergütung bezahlt werde, während im Kanton Graubünden bei einer eingezäunten, nicht wildexponierten Parzelle kein Anspruch auf Entschädigung bestehe.
3.2 Der angefochtene Entscheid ist sorgfältig begründet. Er setzt sich mit den Vorbringen der Beschwerdeführer eingehend auseinander und äussert sich insbesondere auch zum fraglichen, den Kanton Aargau betreffenden Urteil des Bundesgerichts 2C_447/2007 vom 19. Februar 2008. Die entsprechende Argumentation des Verwaltungsgerichts ist erkennbar. Die Beschwerdeführer vermochten sie auch anzufechten. Mehr ist verfassungsrechtlich nicht verlangt.
4. 4.1 Das Bundesrecht schreibt vor, dass der Schaden, den jagdbare Tiere an Wald, landwirtschaftlichen Kulturen und Nutztieren anrichten, angemessen entschädigt wird (Art. 13 Abs. 1 des Bundesgesetzes vom 20. Juni 1986 über die Jagd und den Schutz wildlebender Säugetiere und Vögel [Jagdgesetz, JSG; SR 922.0]). Die nähere Regelung der Entschädigungspflicht obliegt den Kantonen. Allerdings legt das Bundesrecht dafür einen Rahmen fest. Danach ist eine Entschädigung nur zu leisten, wenn es sich nicht um Bagatellschaden handelt und die zumutbaren Massnahmen zur Verhütung von Wildschaden getroffen worden sind. Aufwendungen für Verhütungsmassnahmen können bei der Entschädigung von Wildschaden berücksichtigt werden. Entschädigungen werden nur ausgerichtet, wenn die zumutbaren Massnahmen gegen Wildschäden getroffen wurden (<ref-law>). Im Übrigen verzichtete der Bundesgesetzgeber auf eine detaillierte Regelung. Die Kantone können namentlich bei der näheren Regelung der Entschädigungspflicht der besonderen Situation auf ihrem Territorium Rechnung tragen (vgl. die Urteile des Bundesgerichts 2C_562/2008 vom 28. Januar 2008 E. 2.1 und 2C_447/2007 vom 19. Februar 2008 E. 1.1).
4.2 Der Kanton Graubünden legt die Grundsätze über die Vergütung und Verhütung von Wildschäden in Art. 29 ff. des kantonalen Jagdgesetzes vom 4. Juni 1989 (KJG) fest. Danach sorgt der Kanton mit der Jagd, der Pflege und Nutzung der Lebensräume für Wildbestände, die keine übermässigen Schäden an Wald und landwirtschaftlichen Kulturen verursachen. Der Kanton entschädigt ausser bei Bagatellschäden insbesondere den durch jagdbares Wild und Steinwild verursachten Schaden an landwirtschaftlichen Kulturen. Die Vergütung entfällt oder wird herabgesetzt, wenn der Geschädigte die ihm zumutbaren Abwehrmassnahmen nicht getroffen hat (Art. 32 Abs. 1 und 4 KJG). Gestützt auf Art. 20 und 33 KJG regeln Art. 15 ff. der kantonalen Jagdverordnung vom 29. Mai 1998 (KJV) die Einzelheiten der Beitrags- und Entschädigungspflicht. Art. 17 KJV konkretisiert die zumutbaren Abwehrmassnahmen zur Wildschadensverhütung, während Art. 20 f. KJV die Vergütung und deren Ausschluss bzw. Herabsetzung regeln. Art. 17 lit. a und b KJV bezeichnen insbesondere als zumutbar, gefährdete Intensivkulturen abseits von wildexponierten Gebieten anzulegen und erheblich gefährdete Intensivkulturen einzuzäunen (vgl. das Urteil des Bundesgerichts 2C_562/2008 vom 28. Januar 2008 E. 2.2).
5. 5.1 Im vorliegenden Fall ist die Einschätzung des Verwaltungsgerichts, die Anbaufläche im fraglichen Gebiet "R._" sei aufgrund ihrer Lage nicht wildexponiert, nicht strittig. Die Vorinstanz ging aber davon aus, die Voraussetzungen von Art. 17 lit. a und b KJV seien alternativ und nicht kumulativ. Da die Anbaufläche als erheblich gefährdet einzustufen sei, setze eine Wildschadenvergütung voraus, dass die geschädigte Parzelle über eine taugliche Einzäunung verfügt habe. Der von den Beschwerdeführern angebrachte Zaun sei aber offensichtlich ungenügend gewesen.
5.2 Die bündnerische Regelung der Entschädigungspflicht bei Wildschäden und die Beurteilung des vorliegenden Falles durch die Vorinstanz verletzen die Bundesgesetzgebung über die Jagd nicht. Ersteres entschied das Bundesgericht bereits im Urteil 2C_562/2008. Was den vorliegenden Fall betrifft, konnte sich das Verwaltungsgericht auf die Aussage des Chef-Wildhüters stützen, wonach das fragliche Gebiet als Wildeinstandsgebiet zu bezeichnen sei. Überdies bringen Erdbeerkulturen aufgrund ihres grossen Ertragswertes ein gesteigertes Schadenspotential mit sich und sie verfügen über eine hohe Attraktivität für Wildtiere. Eine hinreichende Einzäunung als Voraussetzung für eine Schadensvergütung zu verlangen, ist den Beschwerdeführern daher zumutbar und widerspricht der Bundesgesetzgebung auch dann nicht, wenn berücksichtigt wird, dass vorliegend die Anbaufläche vom Wald aus erst nach Überschreiten einer Strasse und mehrerer Feldwege und Passierung mehrerer Gehöfte erreicht werden kann. Da für das Gebiet "R._" dasselbe Material verwendet wurde wie im Gebiet "S._", welches ohne Verstoss gegen Bundesrecht als offensichtlich ungenügend beurteilt werden konnte (vgl. das Urteil 2C_562/2008), ist im vorliegenden Fall ebenfalls von der Untauglichkeit der Einzäunung auszugehen. Die Beschwerdeführer räumen dies denn auch sinngemäss ein, wenn sie in ihrer Beschwerdeschrift ausführen, die Zäunung sei "zugegebenermassen im Extrem-Winter 2005/2006 nicht genügend" gewesen. Weshalb aufgrund der unbestrittenermassen harten Bedingungen im fraglichen Winter vom Erfordernis einer tauglichen Einzäunung abzuweichen wäre, ist umso weniger nachvollziehbar, als in einer Gegend, die als Wildeinstandsgebiet gilt, in einem harten Winter erst recht mit einem erhöhten Risiko von Kulturfrass zu rechnen ist.
5.3 Dass die kantonalen Behörden sodann nicht gegen den Grundsatz von Treu und Glauben nach <ref-law> verstossen haben, weil der Wildhüter die bestehende Einzäunung gesehen hat, ohne dagegen etwas einzuwenden, bzw. eine analoge Einrichtung in anderem Zusammenhang gegenüber einer anderen Person als zulässig erachtete, wurde bereits im Urteil 2C_562/2008 dargelegt. Dasselbe gilt für die Frage, ob es die kantonalen Behörden verpassten, nötige geeignete Massnahmen wie zusätzlichen Wildabschuss zu ergreifen. Auch diesen Einwand verwarf das Bundesgericht schon im Urteil 2C_562/2008. Weshalb dies für das Gebiet "R._" anders zu beurteilen wäre, ist nicht ersichtlich.
5.4 Soweit die Beschwerdeführer geltend machen, der angefochtene Entscheid verletze in verfassungswidriger Weise kantonales Recht, erfüllt ihre Argumentation die Anforderungen an eine taugliche Begründung nach Art. 42 Abs. 2 und 106 Abs. 2 BGG weitgehend nicht (vgl. E. 1.3). Die entsprechenden Ausführungen in der Beschwerdeschrift sind vielmehr appellatorischer Natur und legen insbesondere nicht dar, inwiefern der angefochtene Entscheid geradezu unhaltbar sein bzw. gegen das Willkürverbot verstossen sollte. Die allgemein gehaltene Behauptung, <ref-law> sei verletzt, genügt dafür nicht. In diesem Umfang kann daher auf die Beschwerde nicht eingetreten werden. Im Übrigen wäre auch nicht zu erkennen, weshalb der angefochtene Entscheid willkürlich sein sollte.
5.5 Zulässig erscheint immerhin die Rüge, das Rechtsgleichheitsgebot nach <ref-law> sei verletzt, weil im Unterschied zum vorliegenden Fall in einem Parallelfall im Kanton Aargau eine teilweise Vergütung zugesprochen worden sei. Wie das Bundesgericht im - gerade den angerufenen Parallelfall betreffenden - Urteil 2C_447/2007 vom 19. Februar 2008 in E. 3.4 ausführte, bringt es indessen die föderalistische Staatsstruktur der Schweiz mit sich, dass die Kantone in ihrem Zuständigkeitsbereich unterschiedliche Regelungen treffen; eine Verletzung des Grundsatzes der Rechtsgleichheit liegt darin nicht (<ref-ruling> E. 6d S. 179). Gleich verhält es sich, wenn die Beurteilungsspielräume, die bundesrechtliche Normen eröffnen, in den Kantonen in unterschiedlicher Weise ausgefüllt werden (vgl. <ref-ruling> E. 2c). Bei der Beurteilung der Frage, was als zumutbare Massnahme zur Bekämpfung von Wildschäden zu gelten hat, steht den kantonalen Behörden ein solcher Spielraum zu. Sie dürfen dabei auf besondere örtliche Gegebenheiten Rücksicht nehmen. Das bringt es mit sich, dass der eine Kanton eine grosszügigere Regelung oder Praxis kennt als ein anderer Kanton. Die Berufung der Beschwerdeführer auf eine Ungleichbehandlung im interkantonalen Verhältnis geht daher fehl.
6. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang werden die Beschwerdeführer unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und Art. 65 BGG). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Amt für Jagd und Fischerei, dem Bau-, Verkehrs- und Forstdepartement sowie dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, und dem Eidgenössischen Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) schriftlich mitgeteilt.
Lausanne, 26. Januar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Uebersax