Sachverhalt: A. A._, geboren ..., übernahm ab ... 2002 von seiner Ehegattin, geboren ..., die Funktion als Leiter des Seniorenwohnheims Z._ der Einwohnergemeinde X._ (nachfolgend: Arbeitgeberin oder Beschwerdegegnerin). Anlässlich der Sitzung der Alterskommission X._ vom 10. August 2010, an welcher auch A._ teilnahm, informierte der Kommissionspräsident darüber, dass der Gemeinderat "zur Zeit [abkläre], ob die Heime X._ und Y._ künftig zusammengelegt werden könnten." Das Heim X._ werde so künftig als Dépendance von Y._ geführt. Diese Abklärungen seien notwendig, "da zum einen der Heimleiter A._ im Februar 2011 gemäss Reglement das Pensionsalter erreiche und zum anderen die vom Gemeinderat beschlossenen Einsparungen in die Tat umgesetzt werden" müssten. Mit Schreiben vom 15. August 2010 beschwerten sich sechs Mitarbeiterinnen des Seniorenwohnheims beim Präsidenten der Alterskommission über angebliche Mängel in der Heimleitung. Am 22. September 2010 nahm der Heimleiter einen schriftlichen Verweis des Gemeinderates betreffend mangelhaftes Verhalten gegenüber von Heimbewohnerinnen und -bewohnern, organisatorischer Mängel und Verletzungen des Pflichtenheftes sowie Mängel in der Personalführung entgegen. Gleichzeitig überreichten die anwesenden Gemeinderäte A._ eine Vereinbarung "betreffend einvernehmliche Auflösung des Arbeitsverhältnisses als Heimleiter", wonach unter anderem - bei Lohnfortzahlung bis Ende Februar 2011 und Freistellung ab 1. Oktober 2010 - das Arbeitsverhältnis unter Einhaltung der ordentlichen gesetzlichen Kündigungsfrist per 31. Dezember 2010 aufgelöst werden sollte. A._ unterzeichnete diese Vereinbarung, welche auch eine Saldoklausel enthielt, am 27. September 2010 unter Hinzufügung der handschriftlichen Abschlussbemerkung: "P.S. Brief von Anwalt folgt (bin nach wie vor an einer einvernehmlichen Lösung interessiert)". Mit Schreiben datierend vom 27. September 2010 forderte sein Rechtsvertreter neben weiteren Begehren, wie im August zwischen den Parteien besprochen worden sei, solle A._ bis zum Erreichen des ordentlichen AHV-Alters 65 im Februar 2013 bei der Pensionskasse versichert bleiben, wobei die Arbeitgeberin ihre Beiträge zu leisten habe und der Heimleiter seine Arbeitnehmerbeiträge selber einzahlen werde. B. Nachdem bezüglich der verschiedenen Forderungen keine Einigung erzielt werden konnte, liess A._ beim Obergericht Appenzell Ausserrhoden mit verwaltungsgerichtlicher Klage vom 20. Mai 2011 beantragen, die Arbeitgeberin sei zur Bezahlung von Fr. 42'730.- nebst Zins zu 5 % ab 1. März 2012 zu verpflichten (Antrag Ziff. 1); zudem habe sie A._ innert vierzehn Tagen seit Rechtskraft des Urteils ein Arbeitszeugnis zukommen zu lassen (Antrag Ziff. 2). Weil sich die Parteien während der Rechtshängigkeit nicht über den Inhalt des zwischenzeitlich zugestellten Arbeitszeugnisses vom 20. Juni 2011 einigen konnten, hiess das Obergericht die Klage teilweise gut und verpflichtete die Arbeitgeberin, das Arbeitszeugnis vom 20. Juni 2011 um eine bestimmte Textpassage zu ergänzen und erneut wiederum mit Datum vom 20. Juni 2011 A._ zuzustellen. Im Übrigen wies es die Klage ab (Entscheid vom 25. Januar 2012). C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten hält A._ an seinem vorinstanzlichen Antrag Ziff. 1 fest und lässt insoweit die Aufhebung des angefochtenen Entscheides beantragen, als das kantonale Gericht damit Antrag Ziff. 1 der Klage vom 20. Mai 2011 abgewiesen hat. 