Sachverhalt:
A. A._ war seit 1. Februar 2000 als öffentlich-rechtlicher Angestellter für das Amt X._, Kreis Y._, tätig. Auf den 1. Oktober 2001 wurde ihm der Beamtenstatus verliehen. Am 19. Mai 2008 teilte das Departement B._ des Kantons St. Gallen (nachfolgend: Departement) allen Angestellten des Amtes mit, es finde eine Überprüfung der Arbeitsweise und der Organisation statt und die Wiederwahl für die neue Amtsdauer 2008 bis 2012 werde gestützt auf Art. 80 Abs. 2 des Staatsverwaltungsgesetzes vom 16. Juni 1994 (sGS 140.1; StVG) vorerst befristet bis zum Vorliegen der Ergebnisse bzw. bis zur Umsetzung der notwendigen strukturellen und organisatorischen Massnahmen vorgenommen. Je nach Ergebnis werde die Wahl anschliessend für den Rest der Amtsdauer oder bis zur Revision des StVG bestätigt oder es werde die Auflösung des Beamtenverhältnisses eingeleitet. Zudem wurde für alle Beamtenverhältnisse im Zuständigkeitsbereich der Departemente und der Staatskanzlei ein allgemeiner Vorbehalt angebracht, wonach die Wiederwahl nicht für die gesamte Amtsdauer, sondern nur bis zum Zeitpunkt des Vollzugs der Revision des StVG (Aufhebung des Beamtenstatus) erfolge; mit dem Wegfall des Beamtenstatus werde das Dienstverhältnis dann automatisch in ein öffentlich-rechtliches Angestelltenverhältnis überführt.
Mit Schreiben vom 29. Januar 2009 orientierte das Departement die Beamten, dass sie aufgrund der neuen Qualitätsstandards von zwei Personen beurteilt würden. A._ wurde gleichentags zwecks externer Beurteilung persönlich angewiesen, während vorerst dreier Wochen im Kreis Z._ zu arbeiten. Gemäss der zwischen dem Departement, A._ und der Leitung des Amtes X._ abgeschlossenen Vereinbarung vom 10./24. Februar 2009 waren für die Beurteilung E._, Leiter des Amtes X._, und S._, Beamter des Kreises Z._, zuständig. E._ beantragte in der Folge dem Departementsvorsteher mit Brief vom 9. Juni 2009, den Vorbehalt zur Wahl als Beamter nicht aufzuheben und das Arbeitsverhältnis mit A._ aufzulösen. Das Departement teilte A._ gestützt darauf nach einem am 25. Juni 2009 mit ihm geführten Gespräch gleichentags auch noch schriftlich mit, dass eine Auflösung des Beamtenverhältnisses durch Nichtwiederwahl unter Einhaltung einer dreimonatigen Frist gemäss Art. 80 StVG mit sofortiger Freistellung beabsichtigt werde und gewährte ihm das rechtliche Gehör. Mit zwei Schreiben vom 9. Juli 2009 hielt A._ fest, es seien weder formelle noch materielle Gründe für eine Auflösung des Beamtenverhältnisses vorhanden und der Departementsvorsteher habe in dieser Sache in den Ausstand zu treten. Das Departement ordnete am 13. Juli 2009 verfügungsweise an, auf die Wiederwahl von A._ als Beamter werde verzichtet und das Beamtenverhältnis werde unter Einhaltung der dreimonatigen Frist nach Art. 80 StVG per 31. Oktober 2009 aufgelöst, er werde von der weiteren Amtsausübung entbunden und per sofort freigestellt; einer allfälligen Beschwerde gegen die Freistellung wurde die aufschiebende Wirkung entzogen.
B. Nach vorgängiger Ablehnung des Gesuchs um Wiederherstellung der aufschiebenden Wirkung (Präsidialverfügung vom 18. August 2009) wies das Verwaltungsgericht des Kantons St. Gallen die gegen die Verfügung vom 13. Juli 2009 erhobene Beschwerde ab (Entscheid vom 17. Dezember 2009).
C. A._ lässt gegen den Entscheid vom 17. Dezember 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, die Sache sei zur Neubeurteilung an das kantonale Gericht zurückzuweisen. Der Eingabe liegt ein in der Zeitschrift C._ erschienener Bericht über das Amt X._ bei.
Das kantonale Gericht und das Departement schliessen auf Abweisung der Beschwerde.
Erwägungen:
1. 1.1 Der angefochtene Entscheid des Verwaltungsgerichts ist ein Endentscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d, Art. 90 BGG), der ein Beamtenverhältnis betrifft, und somit eine Angelegenheit des öffentlichen Rechts im Sinne von Art. 82 lit. a BGG darstellt. Es handelt sich um eine vermögensrechtliche Streitigkeit, weshalb der Ausschlussgrund von Art. 83 lit. g BGG nicht gegeben ist. Die Streitwertgrenze von Fr. 15'000.- ist erreicht (Art. 85 Abs. 1 lit. b BGG).
1.2 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten können Rechtsverletzungen im Sinne von Art. 95 BGG gerügt werden. Rügen gegen die Sachverhaltsfeststellung sind nur zulässig, wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (BGE 133 II 249 E. 1.2.2 S. 252). Willkür liegt nach der Praxis nicht schon dann vor, wenn eine andere Lösung als die von der Vorinstanz gewählte ebenfalls vertretbar oder gar vorzuziehen wäre, sondern nur dann, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (BGE 134 II 124 E. 4.1 S. 133 mit Hinweisen). Die Rüge, im Rahmen der Sachverhaltsfeststellung sei der grundrechtliche Anspruch auf rechtliches Gehör verletzt worden, kann uneingeschränkt erhoben werden (Urteil 1C_560/2008 vom 6. April 2009 E. 1.2).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. BGE 132 II 257 E. 2.5 S. 262; 130 III 136 E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (BGE 133 II 249 E. 1.4.1 S. 254).
2. Der Beschwerdeführer hat den gegenüber ihm wie auch gegenüber allen andern Angestellten des Amtes X._ am 19. Mai 2008 durch Verfügung eröffneten Vorbehalt bei der Wiederwahl für die am 1. Juni 2008 beginnende neue Amtsdauer 2008 bis 2012 nicht angefochten, weshalb die Rechtmässigkeit dieses Verwaltungsaktes nicht mehr zum Gegenstand dieses Verfahrens gemacht werden kann. Auf die in der Beschwerde erhobene Rüge, der Vorbehalt sei - unzulässigerweise - weniger als drei Monate vor Beginn der neuen Amtsdauer erfolgt (und der kantonale Gerichtsentscheid sei auch aus diesem Grund aufzuheben), kann daher nicht eingetreten werden.
3. 3.1 Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG; BGE 135 V 194). Solche Umstände können namentlich in formellrechtlichen Mängeln des angefochtenen Entscheids liegen, mit denen die Partei nicht rechnete und nach Treu und Glauben nicht zu rechnen brauchte, oder darin, dass die Vorinstanz materiell in einer Weise urteilt, dass bestimmte Sachumstände neu und erstmals rechtserheblich werden. Der vorinstanzliche Verfahrensausgang allein bildet noch keinen hinreichenden Anlass im Sinne von Art. 99 Abs. 1 BGG für die Zulässigkeit von unechten Noven, die bereits im kantonalen Verfahren ohne weiteres hätten vorgebracht werden können (Urteil 9C_920/2008 vom 16. April 2009 E. 2.3, nicht publ. in : BGE 135 V 163, aber in: SVR 2009 BVG Nr. 30 S. 109). Das Vorbringen von Tatsachen oder Beweismitteln, die sich erst nach dem angefochtenen Entscheid ereigneten oder entstanden (sog. echte Noven), ist vor Bundesgericht unzulässig (Urteil 2C_761/2009 vom 18. Mai 2010 E. 4).
3.2 Der Beschwerdeführer lässt vorbringen, soweit erstmals im kantonalen Gerichtsentscheid der Vorwurf erhoben werde, er habe sich über sexuelle Belästigungen durch einen Vorgesetzten beklagt und dadurch das schwer gestörte Betriebsklima (mit-)verursacht, so müsse immerhin darauf hingewiesen werden, dass in der Zwischenzeit - unabhängig von ihm - eine andere Mitarbeiterin des Amtes X._ mit analogen Vorwürfen an die Öffentlichkeit getreten sei, wie dem (neu eingereichten) Bericht über das Amt X._ (publiziert in der Zeitschrift C._) zu entnehmen sei. Ob es sich bei diesem zeitlich nach dem vorinstanzlichen Entscheid vom 17. Dezember 2009 veröffentlichten Bericht um ein zulässiges Novum handelt (Art. 99 Abs. 1 BGG), ist im vorliegenden Verfahren nicht zu prüfen, weil die Beschwerde gemäss den nachfolgenden Erwägungen bereits aus einem anderen Grund gutzuheissen ist.
4. In der letztinstanzlich eingereichten Beschwerdeschrift wird zunächst eine Verletzung des rechtlichen Gehörs nach Art. 29 Abs. 2 BV sowohl durch das Departement B._, unter anderem im Rahmen des Verfügungserlasses wegen mangelnder Begründung, wie auch durch das kantonale Gericht, insbesondere zufolge Substituierung der Verfügungsbegründung durch neue Vorwürfe, zu denen der Beschwerdeführer noch nie habe Stellung nehmen können, gerügt und die Untergrabung des in Art. 29 Abs. 1 BV gewährleisteten Fairnessgebotes im Verwaltungs- und Gerichtsverfahren durch Verneinung einer Befangenheit des zuständigen Departementsvorstehers im vorinstanzlichen Entscheid geltend gemacht.
5. 5.1 Gemäss Art. 29 Abs. 2 BV haben die Parteien Anspruch auf rechtliches Gehör. Das rechtliche Gehör dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung einer Person eingreift. Dazu gehört insbesondere deren Recht, sich vor Erlass des in ihre Rechtsstellung eingreifenden Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (BGE 132 V 368 E. 3.1 S. 370 mit Hinweisen).
Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (BGE 132 II 485 E. 3.2 S. 494; 129 II 497 E. 2.2 S. 504 f., je mit Hinweisen). Im Einzelnen lässt sich nicht generell, sondern nur unter Würdigung der konkreten Interessenlage beurteilen, wie weit das Äusserungsrecht geht. Wegleitend muss der Gedanke sein, einer Partei zu ermöglichen, ihren Standpunkt wirksam zur Geltung zu bringen (BGE 111 Ia 273 E. 2b S. 274; 105 Ia 193 E. 2b/cc S. 197; Urteile 2P.46/2006 vom 7. Juni 2006 E. 4.3, 2P.77/2003 vom 9. Juli 2003 E. 2.1, 2P.241/1996 vom 27. November 1996 E. 2c). Im öffentlichen Dienstrecht können auch relativ informelle Äusserungsgelegenheiten vor der Kündigung dem verfassungsrechtlichen Gehörsanspruch genügen, sofern der betroffenen Person klar war, dass sie mit einer solchen Massnahme zu rechnen hatte. Dabei hat die Partei nicht bloss die ihr zur Last gelegten Tatsachen zu kennen, sondern sie muss darüber hinaus auch wissen, dass gegen sie eine Verfügung mit bestimmter Stossrichtung in Erwägung gezogen wird (Urteil 8C_974/2009 vom 2. Juni 2010 E. 5.2.2).
5.2 Der Umfang des Anspruchs auf rechtliches Gehör wird zunächst durch die kantonalen Verfahrensvorschriften umschrieben. Das Bundesgericht prüft deren Auslegung und Anwendung nur unter dem Gesichtswinkel des Willkürverbotes. Unabhängig vom kantonalen Recht greifen die aus Art. 29 Abs. 2 BV folgenden Verfahrensregeln zur Sicherung des rechtlichen Gehörs Platz (BGE 134 I 159 E. 2.1.1 S. 161). Ob diese Grundsätze eingehalten wurden, prüft das Bundesgericht mit freier Kognition (BGE 124 I 241 E. 2 S. 242 f. mit Hinweisen). Dass sich vorliegend aus dem kantonalen Recht ein weitergehender Gehörsanspruch als aus Art. 29 Abs. 2 BV ergeben würde, wird nicht behauptet und ist auch nicht ersichtlich. Aus Art. 15 des Gesetzes vom 16. Mai 1965 über die Verwaltungsrechtspflege des Kantons St. Gallen (sGS 951.1; VRP), welcher unter anderem bestimmt, dass Verfügungen, die erheblich belasten, nur zulässig sind, wenn die Betroffenen den wesentlichen Sachverhalt kennen und Gelegenheit zur Stellungnahme hatten, lassen sich keine zusätzlichen Aspekte ableiten.
6. 6.1 Das kantonale Gericht ist der Auffassung, die unmissverständliche Mitteilung des Departementes vom 25. Juni 2009, wonach aufgrund der bisherigen Akten und der vorläufigen Beurteilung die Entscheidungsabsicht bestehe, das Beamtenverhältnis aufzulösen, sei zulässig und geboten gewesen. Der Departementsvorsteher habe ausdrücklich festgehalten, dass eine Weiterführung des Arbeitsverhältnisses mit Blick auf die vorgelegten Unterlagen, welche fachliche Mängel aufzeigten, nicht vertretbar sei. Aus dieser Ankündigung sei im Gesamtzusammenhang unmissverständlich hervorgegangen, dass es sich um eine vorläufige Beurteilung, gestützt auf die seinerzeit bekannten Unterlagen, gehandelt habe. Im Kontext habe die Formulierung keinen Anschein der Befangenheit oder Voreingenommenheit zum Ausdruck gebracht. Die Zerstörung des Vertrauensverhältnisses und die Auflösung des Beamtenverhältnisses seien nicht als vollendete Tatsachen dargestellt worden. Der Beschwerdeführer sei zudem bereits in jenem Verfahrensstadium anwaltlich vertreten und damit in der Lage gewesen, die Bedeutung des Schreibens vom 25. Juni 2009 richtig, nämlich als Ausdruck einer vorläufigen Beurteilung, einzuordnen. Der Umstand, dass der Departementsvorsteher den Leiter des Amtes X._ ermächtigt habe, die unmittelbar im Umfeld des Beschwerdeführers tätigen Mitarbeiterinnen und Mitarbeiter auf dieses Schreiben hin, vor der definitiven Entscheidung, über den Stand des Verfahrens zu informieren, sei sachlich haltbar. Die Absicht sei nicht vorbehaltlos gegen aussen, sondern lediglich dem engen Kreis der direkt Betroffenen bekannt gegeben worden, welchen ein Anspruch auf Orientierung zustehe. Dies sei auch im Interesse des Beschwerdeführers gewesen. Zudem seien die materiellen Vorwürfe durchaus geprüft worden, bevor die Absicht zur Auflösung des Dienstverhältnisses mitgeteilt worden sei. Der Departementsvorsteher habe sich "im Rahmen der Gewährung des rechtlichen Gehörs" auf den begründeten Antrag des Amtsleiters stützen und dessen Beurteilung als vorläufige Absicht gegenüber dem Beschwerdeführer zum Ausdruck bringen dürfen.
6.2 Im vorinstanzlichen Entscheid wird mit der in Erwägung 6.1 hiervor zusammengefassten Begründung namentlich eine Voreingenommenheit des Departementsvorstehers im Zeitpunkt des mit Mitteilung vom 25. Juni 2009 dem Beschwerdeführer gewährten rechtlichen Gehörs verneint. Zwar wird im drittletzten Abschnitt dieser Mitteilung lediglich (aber immerhin) die Absicht, das Beamtenverhältnis mit dem Beschwerdeführer durch Nichtwiederwahl aufzulösen und ihn mit der Aussprache der Kündigung sofort freizustellen, kundgetan. Der übrige Text lässt jedoch klar erkennen, dass die Entscheidung zur Nichtfortführung des Dienstverhältnisses in jenem Zeitpunkt bereits gefällt war. So wurde ohne jegliche Einschränkung angegeben, aus den vorgelegten Unterlagen seien fachliche Mängel ersichtlich, "aufgrund derer eine Weiterführung des Arbeitsverhältnisses nicht vertretbar" sei. Das Vertrauensverhältnis zum Beschwerdeführer wurde vorbehaltlos als "zerstört" bezeichnet. Das Schreiben muss unter diesen Umständen klar als Anzeige der Auflösung des Beamtenverhältnisses gewertet werden. Dazu kommt, dass der Leiter des Amtes X._ - auf entsprechende Ermächtigung des Departementsvorstehers hin - bereits am 26. Juni 2009 Drittpersonen über die bevorstehende Auflösung des Beamtenverhältnisses informiert hatte, noch bevor der Beschwerdeführer im Rahmen des ihm eingeräumten rechtlichen Gehörs hätte reagieren können, und über zweieinhalb Wochen vor dem formellen Vollzug der Nichtwiederwahl. Wenn das kantonale Gericht aus diesen Fakten schliesst, die Mitteilung vom 25. Juni 2009 enthalte keine endgültige Entscheidung, sondern nur eine vorläufige Beurteilung der zuständigen Behörde, lässt sich dies auch unter dem eingeschränkten Blickwinkel der Willkür nicht halten. Die zuständige Behörde darf aber erst nach Kenntnisnahme der gesamten entscheidrelevanten Sachlage und mithin nach Anhörung der betroffenen Person zu einer Entscheidung gelangen (Urteil 8C_158/2009 vom 2. September 2009 E. 6.5, nicht publ. in: BGE 136 I 39). Vorliegend kann die Gewährung des rechtlichen Gehörs (der Brief vom 25. Juni 2009 trägt den Titel: "Auflösung Ihres Beamtenverhältnisses: Rechtliches Gehör") mit Blick auf die unmissverständlichen Äusserungen des Regierungsrates nur noch als Leerlauf bezeichnet werden. Stand die Nichtwiederwahl bereits fest, ohne dass sich der Beschwerdeführer dazu vorgängig hat äussern können, so liegt eine Verletzung des rechtlichen Gehörs vor.
7. Ob das rechtliche Gehör auch aus den weiteren, in der Beschwerde geltend gemachten Gründen verletzt ist, kann bei diesem Ergebnis offenbleiben.
8. 8.1 Der vom Departement am 13. Juli 2009 verfügte Verzicht auf die Wiederwahl des Beschwerdeführers als Beamter leidet nach dem Gesagten an einem formellen Mangel. Der Verwaltungsakt und der bestätigende kantonale Gerichtsentscheid sind demgemäss aufzuheben und die Angelegenheit geht an das Departement zurück, damit es sich mit der Frage der Bestätigung der Wiederwahl versus Verzicht auf Wiederwahl ganz neu befasse, dem Versicherten vor einem allfälligen Erlass einer neuen Verfügung nochmals das rechtliche Gehör gewähre und sich in der Folge mit seinen in diesem Rahmen eingebrachten Argumenten inhaltlich auseinandersetze. Der Beschwerdegegner hat in seiner im Rahmen des vorinstanzlichen Verfahrens eingereichten Vernehmlassung zur Beschwerde vom 14. August 2009 ausgeführt, der Verzicht auf die Wiederwahl sei definitiv und bei einer "wider Erwarten" erfolgenden Aufhebung der angefochtenen Verfügung müsste angesichts der anders nicht lösbaren Konfliktsituation in einem neuen Entscheid die Stellvertretung des Departementsvorstehers nach nochmals aufgerolltem Verfahren im Interesse des Amtes und aller Beteiligten "fraglos nochmals genau gleich" verfügen. Angesichts dieser Äusserungen ist abschliessend der Hinweis geboten, dass sich die im Rahmen der höchstrichterlich angeordneten Rückweisung wieder oder allenfalls neu mit der Angelegenheit befassten Personen die Frage stellen sollten, ob sie bereits von vornherein eine feststehende Meinung zur Sache haben. Bejahendenfalls wären andere Personen im Zuständigkeitsbereich des Beschwerdegegners mit der Durchführung des Verfahrens zu betrauen.
8.2 Bei dieser Gelegenheit wird der Beschwerdegegner gegebenenfalls auch die Frage zu überdenken haben, ob die Auflösung eines Beamtenverhältnisses gemäss Art. 80 StVG, bei welchem die Wiederwahl im Sinne von Art. 80 Abs. 2 StVG mit Auflagen verbunden oder von Bedingungen abhängig gemacht wurde, nur dann erfolgen darf, wenn sich die entsprechenden Auflagen oder Bedingungen nicht erfüllt haben, und ob in allen anderen Fällen der nicht fristlosen Auflösung einer der in Art. 77 Abs. 1 StVG genannten Gründe erfüllt sein muss, damit ein Beamtenverhältnis vorzeitig aufgelöst werden darf.
9. 9.1 Der Prozess ist kostenpflichtig (Art. 65 f. BGG). Nach Art. 66 Abs. 1 BGG werden die Gerichtskosten in der Regel der unterliegenden Partei auferlegt. Dem Bund, den Kantonen und den Gemeinden sowie den mit öffentlich-rechtlichen Aufgaben betrauten Organisationen dürfen in der Regel keine Gerichtskosten auferlegt werden, wenn sie in ihrem amtlichen Wirkungskreis und ohne dass es sich um ihr Vermögensinteresse handelt, das Bundesgericht in Anspruch nehmen oder wenn gegen ihre Entscheide in solchen Angelegenheiten Beschwerde geführt worden ist (Art. 66 Abs. 4 BGG).
Im vorliegenden Fall ist der Kanton als Arbeitgeber in seinen Vermögensinteressen betroffen. Der Ausnahmetatbestand von Art. 66 Abs. 4 BGG findet demnach keine Anwendung (BGE 136 I 39), weshalb der unterliegende Beschwerdegegner die Gerichtskosten zu tragen hat (Art. 66 Abs. 1 BGG).
9.2 Das Departement hat dem Beschwerdeführer für das bundesgerichtliche Verfahren ausserdem eine Parteientschädigung zu entrichten (Art. 68 Abs. 1 und 2 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Der Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 17. Dezember 2009 und der Einspracheentscheid des Departementes B._ des Kantons St. Gallen vom 13. Juli 2009 werden aufgehoben. Die Sache wird ans Departement B._ des Kantons St. Gallen zurückgewiesen, damit es im Sinne der Erwägungen verfahre.
2. Die Gerichtskosten von Fr. 3'000.- werden dem Beschwerdegegner auferlegt.
3. Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Verwaltungsgericht des Kantons St. Gallen zurückgewiesen.
5. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Luzern, 23. August 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Berger Götz