Sachverhalt:
Sachverhalt:
A. Dr. med. A._ (Kläger) war seit Mai 1996 als Oberarzt und seit 1997 als leitender Arzt bei der Klinik B._ AG (Beklagte) bzw. bei deren Rechtsvorgängerin tätig. Auf den 1. Januar 1998 stellte die Beklagte Dr. med. C._ als Chefarzt ein. In dieser Funktion war er der Vorgesetzte des Klägers, welcher jedoch seine Stellung als leitender Arzt beibehielt. Im August 1999 wurde die Ehefrau des Chefarztes von der Beklagten als Kardiologin angestellt.
Am 4. September 2000 führten der Verwaltungsratspräsident und am 25. Oktober 2000 der Verwaltungsdirektor der Beklagten je eine Unterredung mit dem Kläger. Mit Schreiben vom 10. November 2000 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger auf den 31. Mai 2001. Als Begründung gab sie an, dass das Vertrauensverhältnis innerhalb der medizinischen Leitung bereits seit geraumer Zeit unüberwindlich zerrüttet sei, was eine weitere Zusammenarbeit verunmögliche. Am 14. Dezember 2000 liess der Kläger der Beklagten mitteilen, dass er die Kündigung als missbräuchlich erachte. In den Monaten Januar und Februar 2001 war der Kläger zeitweise ganz oder teilweise arbeitsunfähig. Auf den 5. Juni 2001 trat er eine neue Stelle an.
Am 4. September 2000 führten der Verwaltungsratspräsident und am 25. Oktober 2000 der Verwaltungsdirektor der Beklagten je eine Unterredung mit dem Kläger. Mit Schreiben vom 10. November 2000 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger auf den 31. Mai 2001. Als Begründung gab sie an, dass das Vertrauensverhältnis innerhalb der medizinischen Leitung bereits seit geraumer Zeit unüberwindlich zerrüttet sei, was eine weitere Zusammenarbeit verunmögliche. Am 14. Dezember 2000 liess der Kläger der Beklagten mitteilen, dass er die Kündigung als missbräuchlich erachte. In den Monaten Januar und Februar 2001 war der Kläger zeitweise ganz oder teilweise arbeitsunfähig. Auf den 5. Juni 2001 trat er eine neue Stelle an.
B. Mit Klage vom 26. Oktober 2001 verlangte der Kläger vor Kantonsgericht von Appenzell A.Rh. im Wesentlichen die Verpflichtung der Beklagten zur Zahlung von Fr. 150'000.-- nebst Zins. Die Klage wurde mit Urteil vom 1. Juli 2002 im Betrag von Fr. 18'613.05 netto nebst 5 % Zins seit 5. Juni 2001 gutgeheissen. Das Kantonsgericht hielt die Kündigung aufgrund der nachgewiesenen Tatumstände nicht für missbräuchlich. Es sprach dem Kläger jedoch für die Zeit vom 1. bis zum 4. Juni 2001 Lohn von Fr. 2'239.80 zu, für Hintergrunddienst Dezember 2000 - Mai 2001 Fr. 1'392.90 sowie als Abgeltung des Ferienanspruchs Fr. 14'980.35 für 23 Tage. Hinsichtlich der Entschädigung für nicht bezogene Ferien erwog das Kantonsgericht, der Kläger habe sich einen Drittel der nicht durch Krankheit dahingefallenen Freistellungszeit, mithin 1,75 Monate, auf sein Ferienguthaben von 60,52 Tagen anrechnen zu lassen.
B. Mit Klage vom 26. Oktober 2001 verlangte der Kläger vor Kantonsgericht von Appenzell A.Rh. im Wesentlichen die Verpflichtung der Beklagten zur Zahlung von Fr. 150'000.-- nebst Zins. Die Klage wurde mit Urteil vom 1. Juli 2002 im Betrag von Fr. 18'613.05 netto nebst 5 % Zins seit 5. Juni 2001 gutgeheissen. Das Kantonsgericht hielt die Kündigung aufgrund der nachgewiesenen Tatumstände nicht für missbräuchlich. Es sprach dem Kläger jedoch für die Zeit vom 1. bis zum 4. Juni 2001 Lohn von Fr. 2'239.80 zu, für Hintergrunddienst Dezember 2000 - Mai 2001 Fr. 1'392.90 sowie als Abgeltung des Ferienanspruchs Fr. 14'980.35 für 23 Tage. Hinsichtlich der Entschädigung für nicht bezogene Ferien erwog das Kantonsgericht, der Kläger habe sich einen Drittel der nicht durch Krankheit dahingefallenen Freistellungszeit, mithin 1,75 Monate, auf sein Ferienguthaben von 60,52 Tagen anrechnen zu lassen.
C. Beide Parteien appellierten gegen das Urteil vom 1. Juli 2002. Das Obergericht von Appenzell A.Rh. verpflichtete die Beklagte am 18. November 2003, dem Kläger den Betrag von Fr. 44'873.85 brutto nebst 5 % Zins seit 5. Juni 2001 (Lohn 1.-4. Juni 2001 und Ferienentschädigung) zu bezahlen. Im Mehrbetrag wies es die Klage ab. Darüber hinaus nahm das Obergericht davon Vormerk, dass die Beklagte die Klage im Umfang von Fr. 1'500.-- brutto nebst 5 % Zins seit 5. Juni 2001 (Entschädigung Hintergrunddienst) anerkannt hat. Wie das erstinstanzliche Gericht kam auch das Obergericht zum Ergebnis, dass die Kündigung nicht missbräuchlich sei. Hingegen schützte das Obergericht die Berufung des Klägers betreffend die Position Ferienentschädigung. Es hielt fest, die Beklagte habe mit der Freistellung unmissverständlich die Weisung an den Kläger verbunden, sich während der Freistellungsdauer der Arbeitnehmerin zur Verfügung zu halten. Diese Anordnung habe bis zum Ausscheiden des Klägers aus dem Arbeitsverhältnis mit der Beklagten bestanden. Dass sich der Kläger während der Freistellung mehrheitlich in Karlsruhe aufgehalten habe, sei auf die Kündigung der Wohnung des Klägers in der Klinik zurückzuführen. Der Arbeitnehmer sei nie aufgefordert worden, sich eine Unterkunft in der Nähe des Arbeitsortes zu suchen. Unter diesen Umständen stehe die Weisung der Arbeitgeberin an den Arbeitnehmer, sich zur Verfügung zu halten, dessen Pflicht zum Bezug von Ferientagen während der Freistellungsdauer entgegen. Die Beklagte habe dem Kläger daher das volle Guthaben von 60,52 Ferientagen, insgesamt Fr. 42'448.75 nebst Zins, zu vergüten. Auf Appellation der Beklagten bestätigte die Vorinstanz ferner das erstinstanzliche Urteil, soweit damit die Abgeltung des Lohnes für die Zeit vom 1.-4. Juni 2001 angeordnet worden war.
C. Beide Parteien appellierten gegen das Urteil vom 1. Juli 2002. Das Obergericht von Appenzell A.Rh. verpflichtete die Beklagte am 18. November 2003, dem Kläger den Betrag von Fr. 44'873.85 brutto nebst 5 % Zins seit 5. Juni 2001 (Lohn 1.-4. Juni 2001 und Ferienentschädigung) zu bezahlen. Im Mehrbetrag wies es die Klage ab. Darüber hinaus nahm das Obergericht davon Vormerk, dass die Beklagte die Klage im Umfang von Fr. 1'500.-- brutto nebst 5 % Zins seit 5. Juni 2001 (Entschädigung Hintergrunddienst) anerkannt hat. Wie das erstinstanzliche Gericht kam auch das Obergericht zum Ergebnis, dass die Kündigung nicht missbräuchlich sei. Hingegen schützte das Obergericht die Berufung des Klägers betreffend die Position Ferienentschädigung. Es hielt fest, die Beklagte habe mit der Freistellung unmissverständlich die Weisung an den Kläger verbunden, sich während der Freistellungsdauer der Arbeitnehmerin zur Verfügung zu halten. Diese Anordnung habe bis zum Ausscheiden des Klägers aus dem Arbeitsverhältnis mit der Beklagten bestanden. Dass sich der Kläger während der Freistellung mehrheitlich in Karlsruhe aufgehalten habe, sei auf die Kündigung der Wohnung des Klägers in der Klinik zurückzuführen. Der Arbeitnehmer sei nie aufgefordert worden, sich eine Unterkunft in der Nähe des Arbeitsortes zu suchen. Unter diesen Umständen stehe die Weisung der Arbeitgeberin an den Arbeitnehmer, sich zur Verfügung zu halten, dessen Pflicht zum Bezug von Ferientagen während der Freistellungsdauer entgegen. Die Beklagte habe dem Kläger daher das volle Guthaben von 60,52 Ferientagen, insgesamt Fr. 42'448.75 nebst Zins, zu vergüten. Auf Appellation der Beklagten bestätigte die Vorinstanz ferner das erstinstanzliche Urteil, soweit damit die Abgeltung des Lohnes für die Zeit vom 1.-4. Juni 2001 angeordnet worden war.
D. Der Kläger hat das Urteil des Obergerichts von Appenzell A.Rh. vom 18. November 2003 mit eidgenössischer Berufung beim Bundesgericht angefochten. Er beantragt, die Beklagte zu verpflichten, ihm Fr. 105'126.15 nebst 5 % Zins seit dem 5. Juni 2001 zu bezahlen. Die Beklagte schliesst auf Abweisung der Berufung, soweit darauf eingetreten werden könne, und sie erhebt Anschlussberufung mit dem Rechtsbegehren, die Forderung des Klägers von Fr. 42'448.75 (Ferienentschädigung) abzuweisen und diesem nur noch Fr. 2'425.10 zuzusprechen; eventuell die Streitsache zur Entscheidung in diesem Punkte an die Vorinstanz zurückzuweisen. Der Kläger stellt den Antrag, die Anschlussberufung abzuweisen.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Nach Art. 55 Abs. 1 lit. c OG ist in der Berufungsschrift anzugeben, welche Bundesrechtssätze der angefochtene Entscheid verletzt und inwiefern er gegen sie verstösst. Nach der Praxis des Bundesgerichts ist unerlässlich, dass in der Berufungsschrift auf die Begründung des angefochtenen Urteils eingegangen und im Einzelnen dargetan wird, worin eine Verletzung von Bundesrecht liegen soll (<ref-ruling> E. 2a S. 400). Unzulässig sind dagegen Rügen, die sich gegen die tatsächlichen Feststellungen und gegen die Beweiswürdigung der Vorinstanz richten, es sei denn, es werden zugleich substanziierte Rügen im Sinne von Art. 63 Abs. 2 OG (offensichtliches Versehen) oder Art. 64 OG (unvollständige Ermittlung des Sachverhalts) erhoben (Art. 55 Abs. 1 lit. c OG; <ref-ruling> E. 1f S. 393). Wer sich auf solche Ausnahmen von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der letzten kantonalen Instanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat darüber genaue Angaben mit Aktenhinweisen zu machen (<ref-ruling> E. 2a S. 485 f.). Auf die Berufung ist im Folgenden nur einzutreten, soweit der Kläger diese Vorschriften beachtet.
1.2 Die Vorinstanz hat festgestellt, zu den Unstimmigkeiten zwischen dem Kläger und dem Chefarzt habe die tendenzielle Abwehrhaltung des Klägers gegenüber einer Strukturveränderung, die er offenbar mit einem grossen Teil des Personals geteilt habe, nicht unwesentlich beigetragen. Hinzu gekommen sei die Unverträglichkeit des Klägers mit der Ehefrau des Chefarztes, deren Anstellung ein Element der Strukturveränderung dargestellt habe.
Von diesem von der Vorinstanz für das Bundesgericht verbindlich festgestellten Sachverhalt weicht der Kläger ab, wenn er in der Berufung behauptet, bei der Kündigung habe nicht die Unverträglichkeit des Klägers mit der Ehefrau des Chefarztes, sondern deren Integration und Akzeptanz in der Klinik im Vordergrund gestanden. Dasselbe gilt für das Vorbringen des Klägers, er habe sich nie gegen Strukturveränderungen, sondern lediglich gegen die einseitige Vertragsänderung zur Wehr gesetzt. Zwar kann nach der Rechtsprechung Missbrauch vorliegen, wenn eine unbillige Änderung der Lohn- und Arbeitsbedingungen durchgesetzt werden soll, für die weder marktbedingte noch betriebliche Gründe bestehen, und die Kündigung als Druckmittel verwendet wird, um den Arbeitnehmer zu einem bestimmten Verhalten zu bewegen (<ref-ruling> E. 3b). Der Kläger legt indessen nicht rechtsgegnügend dar, welche Abmachungen die Beklagte von sich aus geändert hat und inwiefern die Vorinstanz folglich Bundesrecht verletzt haben soll, weil sie nicht auf die Unzulässigkeit der betreffenden Vertragsänderung schloss. Insoweit kann auf die Berufung nicht eingetreten werden.
Von diesem von der Vorinstanz für das Bundesgericht verbindlich festgestellten Sachverhalt weicht der Kläger ab, wenn er in der Berufung behauptet, bei der Kündigung habe nicht die Unverträglichkeit des Klägers mit der Ehefrau des Chefarztes, sondern deren Integration und Akzeptanz in der Klinik im Vordergrund gestanden. Dasselbe gilt für das Vorbringen des Klägers, er habe sich nie gegen Strukturveränderungen, sondern lediglich gegen die einseitige Vertragsänderung zur Wehr gesetzt. Zwar kann nach der Rechtsprechung Missbrauch vorliegen, wenn eine unbillige Änderung der Lohn- und Arbeitsbedingungen durchgesetzt werden soll, für die weder marktbedingte noch betriebliche Gründe bestehen, und die Kündigung als Druckmittel verwendet wird, um den Arbeitnehmer zu einem bestimmten Verhalten zu bewegen (<ref-ruling> E. 3b). Der Kläger legt indessen nicht rechtsgegnügend dar, welche Abmachungen die Beklagte von sich aus geändert hat und inwiefern die Vorinstanz folglich Bundesrecht verletzt haben soll, weil sie nicht auf die Unzulässigkeit der betreffenden Vertragsänderung schloss. Insoweit kann auf die Berufung nicht eingetreten werden.
2. 2.1 Missbräuchlich ist eine Kündigung, wenn sie aus bestimmten unzulässigen Gründen ausgesprochen wird, die in <ref-law> umschrieben werden. Die Aufzählung in <ref-law> ist allerdings nicht abschliessend. Sie konkretisiert vielmehr das allgemeine Rechtsmissbrauchsverbot und gestaltet dieses mit für den Arbeitsvertrag geeigneten Rechtsfolgen aus. Sogenanntes Mobbing an sich begründet den Missbrauch des Kündigungsrechts nicht ohne weiteres. Missbräuchlich kann eine Kündigung allerdings sein, wenn sie wegen einer Leistungseinbusse des Arbeitnehmers ausgesprochen wurde, welche sich ihrerseits als Folge des Mobbing erweist. Denn die Ausnutzung eigenen rechtswidrigen Verhaltens bildet einen typischen Anwendungsfall des Rechtsmissbrauchs. Der Arbeitgeber, der Mobbing nicht verhindert, verletzt seine Fürsorgepflicht (<ref-law>). Er darf die Kündigung nicht mit den Folgen seiner eigenen Vertragsverletzung rechtfertigen (<ref-ruling> E. 2a mit Hinweisen).
2.2 Die Vorinstanz verneinte eine Verletzung der Fürsorgepflicht im Sinne von <ref-law> durch die Beklagte. Sie hielt fest, aufgrund des schlechten Betriebsklimas habe sich der Verwaltungsrat der Beklagten nach verschiedenen Einzelgesprächen mit dem Kader, unter anderem auch mit dem Kläger und dem Chefarzt, zur Kündigung des Arbeitsverhältnisses mit dem Kläger entschieden. Um das Funktionieren der medizinischen Leitung wiederherzustellen bzw. die zwischenmenschlichen Spannungen zwischen dem Kläger einerseits und dem Chefarzt und dessen Ehefrau andererseits zu beseitigen, welche Ursache des schlechten Betriebsklimas gebildet hätten, habe die Beklagte von den beiden Möglichkeiten, entweder den Kläger oder den Chefarzt und dessen Ehefrau zu entlassen, die erste gewählt. Damit habe sie ihren Ermessensspielraum nicht zu Lasten des Klägers überschritten. Mit den beschriebenen Einzelanhörungen der Betroffenen sei sie dabei durchaus angemessen vorgegangen.
2.3 Der Kläger bringt in der Berufung sinngemäss vor, die Vorinstanz habe verkannt, dass es die Beklagte unterlassen habe, zumutbare Massnahmen zu ergreifen, um die Lage zu entspannen. Die Beklagte habe nämlich "kein gemeinsames Gespräch ermöglicht, keine Weisungen und Ermahnungen erteilt, keine organisatorischen Veränderungen vorgenommen". Indem die Beklagte lediglich die Situation bewertet und danach beschlossen habe, es sei am einfachsten, das Arbeitsverhältnis mit dem Kläger aufzulösen, habe sie ihre Fürsorgepflicht missachtet.
2.4 Die Rüge ist unbegründet. Der Berufung ist nicht zu entnehmen, welche Weisungen und Ermahnungen die Beklagte hätte erteilen und an wen diese hätten gerichtet sein müssen. Es lässt sich daher nicht beurteilen, ob es zur Fürsorgepflicht der Beklagten gehört hätte, vor der Auflösung des Arbeitsverhältnisses "Weisungen und Ermahnungen" auszusprechen. Dasselbe gilt für die implizit erhobene Behauptung des Klägers, die Beklagte hätte organisatorische Veränderungen anordnen müssen, denn der Kläger erläutert mit keinem Wort, wie derartige Massnahmen zu seinem Schutze hätten ausgestaltet werden müssen. Insoweit fehlt es der Berufung an der nötigen Begründung, weshalb darauf nicht einzutreten ist. Zuzugestehen ist dem Kläger aber, dass unklar bleibt, weshalb die Beklagte ein gemeinsames Gespräch unter den vom Konflikt betroffenen Personen nicht für tunlich erachtete. Selbst wenn jedoch ein solches Gespräch angezeigt gewesen wäre, hätte dessen Ausbleiben nicht ohne Weiteres die Missbräuchlichkeit der Kündigung zur Folge, zumal der Kläger nicht behauptet, er habe eine Aussprache mit einem Exponenten der Klinikleitung und dem Chefarzt und dessen Ehefrau gefordert.
2.4 Die Rüge ist unbegründet. Der Berufung ist nicht zu entnehmen, welche Weisungen und Ermahnungen die Beklagte hätte erteilen und an wen diese hätten gerichtet sein müssen. Es lässt sich daher nicht beurteilen, ob es zur Fürsorgepflicht der Beklagten gehört hätte, vor der Auflösung des Arbeitsverhältnisses "Weisungen und Ermahnungen" auszusprechen. Dasselbe gilt für die implizit erhobene Behauptung des Klägers, die Beklagte hätte organisatorische Veränderungen anordnen müssen, denn der Kläger erläutert mit keinem Wort, wie derartige Massnahmen zu seinem Schutze hätten ausgestaltet werden müssen. Insoweit fehlt es der Berufung an der nötigen Begründung, weshalb darauf nicht einzutreten ist. Zuzugestehen ist dem Kläger aber, dass unklar bleibt, weshalb die Beklagte ein gemeinsames Gespräch unter den vom Konflikt betroffenen Personen nicht für tunlich erachtete. Selbst wenn jedoch ein solches Gespräch angezeigt gewesen wäre, hätte dessen Ausbleiben nicht ohne Weiteres die Missbräuchlichkeit der Kündigung zur Folge, zumal der Kläger nicht behauptet, er habe eine Aussprache mit einem Exponenten der Klinikleitung und dem Chefarzt und dessen Ehefrau gefordert.
3. 3.1 Der Missbrauch einer Kündigung kann sich aus der Art und Weise ergeben, wie die kündigende Partei ihr Recht ausübt. Selbst wenn eine Partei die Kündigung rechtmässig erklärt, muss sie das Gebot schonender Rechtsausübung beachten. Sie darf insbesondere kein falsches und verdecktes Spiel treiben, das Treu und Glauben krass widerspricht (<ref-ruling> E. 2b; <ref-ruling> E. 4b/bb und cc).
3.2 Der Kläger hat die Kündigung im kantonalen Verfahren auch wegen des Vorgehens der Beklagten als missbräuchlich dargestellt.
3.2.1 Die Beklagte habe ihm gegenüber den Willen zur Fortsetzung des Arbeitsverhältnisses vorgetäuscht, obwohl sie bereits mit anderen Bewerbern Vertragsverhandlungen geführt habe. Das Kantonsgericht, auf dessen Erwägungen die Vorinstanz verweist, führte dazu aus, der Kläger habe seine Behauptung mit einer einzigen Bewerbung untermauert, welche nicht an die Klinik, sondern an den Chefarzt persönlich gerichtet gewesen sei. Die Vorinstanz hielt daher nicht für nachgewiesen, dass bereits in diesem frühen Stadium konkrete Vertragsverhandlungen aufgenommen worden wären. Dass es gar zum Abschluss eines Arbeitsvertrages gekommen wäre, habe der Kläger nicht behauptet.
3.2.2 Dieser Argumentation hält der Kläger in der Berufung entgegen, die Ausschreibung der Stelle beweise, dass die Beklagte bereits im August die Absicht gehegt habe, das Arbeitsverhältnis mit dem Kläger aufzulösen oder mindestens dessen Fortsetzung ernsthaft in Frage zu stellen, ohne dass sie den Kläger hierüber in Kenntnis gesetzt hätte.
3.2.3 Der Kläger verkennt, dass die kantonalen Gerichte nicht davon ausgegangen sind, die Beklagte habe die Stelle des Klägers ausgeschrieben. Der Kläger erhebt diesbezüglich keine substanziierten Sachverhaltsrügen. Damit ist seinem Einwand die Grundlage entzogen.
3.2.3 Der Kläger verkennt, dass die kantonalen Gerichte nicht davon ausgegangen sind, die Beklagte habe die Stelle des Klägers ausgeschrieben. Der Kläger erhebt diesbezüglich keine substanziierten Sachverhaltsrügen. Damit ist seinem Einwand die Grundlage entzogen.
3.3 3.3.1 Ebenfalls im Sinne einer Kritik am Vorgehen der Beklagten bei der Kündigung hat der Kläger im kantonalen Verfahren vorgetragen, dass der Entscheid über die Kündigung zwischen dem Chefarzt und dem Verwaltungsdirektor der Beklagten sowie dem Vorsitzenden des medizinischen Beirates abgesprochen worden sei, während er selbst über die Kündigungsabsichten im Dunkeln gelassen worden sei. Der Chefarzt habe auch den leitenden Arzt der psychosomatischen Abteilung und den Leiter der Hotellerie über die Kündigung informiert, bevor er den Kläger darüber unterrichtet habe.
3.3.2 Die Vorinstanz liess offen, ob diese Behauptung zutraf, weil sie in rechtlicher Hinsicht davon ausging, es liege im Rahmen einer zulässigen Informationspolitik, die Geschäftsleitung und einen Teil des Kaders über eine bevorstehende Auflösung des Arbeitsverhältnisses mit einem anderen Kadermitglied ins Bild zu setzen.
3.3.3 Der Kläger macht mit der Berufung geltend, entgegen der Auffassung der Vorinstanz habe die Beklagte ein falsches und verdecktes Spiel betrieben und dadurch den Grundsatz von Treu und Glauben krass verletzt. Insbesondere habe sie gar nicht erst versucht, die Situation zu ändern, sondern mit der Kündigung dem Kläger die Rechnung für eine quasi schicksalhafte, unabänderliche Situation präsentiert. Es widerspreche den Gepflogenheiten und Grundsätzen eines fürsorglichen Arbeitgeberverhaltens zuzulassen, dass ein Mitarbeiter über Dritte von seiner bevorstehenden Entlasssung erfahre und dass alsdann die Kündigung ohne jegliches Kündigungs- oder Austrittsgespräch auf dem Korrespondenzweg ohne Angabe von Gründen ausgesprochen werde.
3.3.4 Auch diese Vorbringen sind zu allgemein gehalten, als dass daraus auf eine Verletzung der Treue- oder Fürsorgepflicht des Arbeitgebers geschlossen werden könnte, soweit sie nicht auf einem Sachverhalt beruhen, der dem angefochtenen Urteil nicht zu entnehmen ist. Der Kläger zeigt wiederum nicht auf, welche Massnahmen die Beklagte hätte ergreifen können, um die untragbar gewordene Situation auch ohne eine Kündigung des Klägers zu entschärfen. Auf die Erwägung der Vorinstanz, die Information der Geschäftsleitung und bestimmter Kadermitglieder über eine bevorstehende Kündigung vor deren Vornahme sei nicht unbedingt treuwidrig, geht der Kläger nicht ein. Er beschränkt sich darauf, im Widerspruch zu den Feststellungen im angefochtenen Urteil zu behaupten, er habe von Dritten über seine bevorstehende Entlassung erfahren. Ebenso wenig geht aus dem angefochtenen Urteil hervor, dass der Kläger die Missbräuchlichkeit der Kündigung mit dem Fehlen eines Austrittsgesprächs begründet hat. Auf den erstmals im Berufungsverfahren erhobenen Einwand ist nicht einzutreten (Art. 55 Abs. 1 lit c OG). Inwiefern die Vorinstanz gegen <ref-law> bzw. gegen <ref-law> verstossen haben soll, legt der Kläger nicht rechtsgenügend dar und ist nicht ersichtlich.
3.3.4 Auch diese Vorbringen sind zu allgemein gehalten, als dass daraus auf eine Verletzung der Treue- oder Fürsorgepflicht des Arbeitgebers geschlossen werden könnte, soweit sie nicht auf einem Sachverhalt beruhen, der dem angefochtenen Urteil nicht zu entnehmen ist. Der Kläger zeigt wiederum nicht auf, welche Massnahmen die Beklagte hätte ergreifen können, um die untragbar gewordene Situation auch ohne eine Kündigung des Klägers zu entschärfen. Auf die Erwägung der Vorinstanz, die Information der Geschäftsleitung und bestimmter Kadermitglieder über eine bevorstehende Kündigung vor deren Vornahme sei nicht unbedingt treuwidrig, geht der Kläger nicht ein. Er beschränkt sich darauf, im Widerspruch zu den Feststellungen im angefochtenen Urteil zu behaupten, er habe von Dritten über seine bevorstehende Entlassung erfahren. Ebenso wenig geht aus dem angefochtenen Urteil hervor, dass der Kläger die Missbräuchlichkeit der Kündigung mit dem Fehlen eines Austrittsgesprächs begründet hat. Auf den erstmals im Berufungsverfahren erhobenen Einwand ist nicht einzutreten (Art. 55 Abs. 1 lit c OG). Inwiefern die Vorinstanz gegen <ref-law> bzw. gegen <ref-law> verstossen haben soll, legt der Kläger nicht rechtsgenügend dar und ist nicht ersichtlich.
4. Die Berufung des Klägers erweist sich weitgehend als unzulässig und ist im Übrigen unbegründet.
4. Die Berufung des Klägers erweist sich weitgehend als unzulässig und ist im Übrigen unbegründet.
5. 5.1 Mit der Anschlussberufung macht die Beklagte geltend, der Vorinstanz sei ein offensichtliches Versehen gemäss Art. 63 Abs. 2 OG unterlaufen, als sie feststellte, die Beklagte habe nicht behauptet, sie sei während der Freistellungsdauer in irgendeiner Weise auf ihre schriftliche Anordnung zurückgekommen, dass sich der Kläger während der Kündigungszeit der Beklagten zur Verfügung halten müsse. In der erstinstanzlichen Klageantwort habe die Beklagte ausgeführt, dass die Weisung als Floskel ohne entsprechenden Willen der Beklagten in das Kündigungsschreiben hineingeraten sei und dass der Verwaltungsdirektor dem Kläger auch mündlich zu verstehen gegeben habe, dass er durchaus verfügen könne. In der erstinstanzlichen Duplik habe sie sodann den Kläger beim Zugeständnis behaftet, dass seine Anwesenheit in der Klinik B._ nicht erwünscht gewesen sei, und sie habe beigefügt, dass ein schriftlicher Widerruf "der Floskel" somit unnötig gewesen sei. In der Appellationsbegründung habe sie nochmals festgehalten, dass der Kläger frei über seine verbleibenden Ferientage habe verfügen können. In der Appellationsantwort schliesslich habe sie nochmals auf ihre einschlägigen Rechtsschriften hingewiesen.
5.2 Nach der Rechtsprechung liegt ein offensichtliches Versehen im Sinne von Art. 63 Abs. 2 OG nur vor, wenn die Vorinstanz eine bestimmte Aktenstelle übersehen oder unrichtig, d.h. nicht in ihrer wahren Gestalt, insbesondere nicht in ihrem wirklichen Wortlaut wahrgenommen hat (<ref-ruling> E. 2a). Betrifft das Versehen nur einen Ausschnitt der Beweiswürdigung, z.B. ein einzelnes Indiz einer Indizienkette oder eine von mehreren Zeugenaussagen, so hilft die Versehensrüge nicht weiter; diesfalls läuft die Rüge auf eine unzulässige Kritik an der Beweiswürdigung hinaus und ist daher von vornherein nicht zu hören (Messmer/Imboden, Die eidgenössischen Rechtsmittel in Zivilsachen, S. 138).
5.2 Nach der Rechtsprechung liegt ein offensichtliches Versehen im Sinne von Art. 63 Abs. 2 OG nur vor, wenn die Vorinstanz eine bestimmte Aktenstelle übersehen oder unrichtig, d.h. nicht in ihrer wahren Gestalt, insbesondere nicht in ihrem wirklichen Wortlaut wahrgenommen hat (<ref-ruling> E. 2a). Betrifft das Versehen nur einen Ausschnitt der Beweiswürdigung, z.B. ein einzelnes Indiz einer Indizienkette oder eine von mehreren Zeugenaussagen, so hilft die Versehensrüge nicht weiter; diesfalls läuft die Rüge auf eine unzulässige Kritik an der Beweiswürdigung hinaus und ist daher von vornherein nicht zu hören (Messmer/Imboden, Die eidgenössischen Rechtsmittel in Zivilsachen, S. 138).
5.3 5.3.1 Dem erstinstanzlichen Gericht erschien als "gänzlich unglaubwürdig", dass die Beklagte den Zusatz als bedeutungslose Floskel verstanden hat. Sie hielt den Kläger zudem für berechtigt, nach Treu und Glauben anzunehmen, er müsse sich bis zum Ende der Kündigungsfrist zur Verfügung halten. Dass unter diesen Umständen nach kantonalem Prozessrecht ein globaler Hinweis auf die einschlägigen Ausführungen im erstinstanzlichen Urteil in der Appellationsantwort bzw. die Formulierung in der Appellationsbegründung, der Kläger könne frei über seine verbleibenden Ferientage verfügen, als Behauptung gelten muss, die Beklagte sei während der Freistellungsdauer auf ihre Anordnung zurückgekommen, legt die Beklagte nicht dar und ist nicht ersichtlich. Von einem offensichtlichen Versehen kann nicht die Rede sein, sondern es liegt Beweiswürdigung vor, die im bundesgerichtlichen Berufungsverfahren nicht kritisiert werden kann.
5.3.2 Die Beklagte behauptet sodann eine Verletzung ihres Beweisführungsanspruchs nach <ref-law>. Sie bringt vor, die Vorinstanz habe ausser Acht gelassen, dass sie vor dem erstinstanzlichen Gericht für ihre Behauptung, der Verwaltungsdirektor habe dem Kläger mündlich zu verstehen gegeben, dieser könne verfügen, einen Zeugen offeriert habe. Sie legt indessen nicht dar, dass sie ihren Beweisantrag vor Obergericht erneuert hat. Unter diesen Umständen kann der Vorinstanz keine Verletzung von <ref-law> vorgeworfen werden, wenn sie den erstinstanzlich angebotenen Zeugen nicht von Amtes wegen angehört hat.
5.3.2 Die Beklagte behauptet sodann eine Verletzung ihres Beweisführungsanspruchs nach <ref-law>. Sie bringt vor, die Vorinstanz habe ausser Acht gelassen, dass sie vor dem erstinstanzlichen Gericht für ihre Behauptung, der Verwaltungsdirektor habe dem Kläger mündlich zu verstehen gegeben, dieser könne verfügen, einen Zeugen offeriert habe. Sie legt indessen nicht dar, dass sie ihren Beweisantrag vor Obergericht erneuert hat. Unter diesen Umständen kann der Vorinstanz keine Verletzung von <ref-law> vorgeworfen werden, wenn sie den erstinstanzlich angebotenen Zeugen nicht von Amtes wegen angehört hat.
6. Schliesslich kritisiert die Beklagte als Verstoss gegen <ref-law> bzw. <ref-law> in Verbindung mit <ref-law>, dass die Vorinstanz in der kurz nach Auflösung des Arbeitsverhältnisses erfolgten Wohnungskündigung nicht einen Umstand erblickte, dem der Kläger nach Treu und Glauben hätte entnehmen müssen, die Beklagte widerrufe ihre Weisung.
Die Rüge ist offensichtlich unbegründet. Angesichts der klaren, schriftlichen Anweisung, er habe sich bis zum Ablauf der Kündigungsfrist der Beklagten zur Verfügung zu halten, musste der Kläger auch durch den Erhalt der Wohnungskündigung nicht zur Überzeugung gelangen, die Beklagte verzichte ab dem Auszugstermin gänzlich auf seine Dienste. Er konnte vielmehr in guten Treuen annehmen, dass die Beklagte ihre Weisung gegebenenfalls ebenso klar und unmissverständlich zurücknehmen werde, wie sie diese ausgesprochen hatte, zumal aus dem angefochtenen Urteil nicht hervorgeht, dass die Kündigung der Wohnung die Unmöglichkeit bewirkt hatte, den Kläger zur Arbeit abzurufen. Ob anders zu entscheiden wäre, wenn die von der Beklagten angeführte mündliche Äusserung des Verwaltungsdirektors nachgewiesen wäre, erscheint fraglich, kann aber offen bleiben. Jedenfalls ist nicht ersichtlich, woraus der Kläger zweifelsfrei auf einen Verzicht der Beklagten auf seine Arbeitsbereitschaft hätte schliessen müssen. Auch in dieser Hinsicht hält das angefochtene Urteil vor Bundesrecht stand.
Die Rüge ist offensichtlich unbegründet. Angesichts der klaren, schriftlichen Anweisung, er habe sich bis zum Ablauf der Kündigungsfrist der Beklagten zur Verfügung zu halten, musste der Kläger auch durch den Erhalt der Wohnungskündigung nicht zur Überzeugung gelangen, die Beklagte verzichte ab dem Auszugstermin gänzlich auf seine Dienste. Er konnte vielmehr in guten Treuen annehmen, dass die Beklagte ihre Weisung gegebenenfalls ebenso klar und unmissverständlich zurücknehmen werde, wie sie diese ausgesprochen hatte, zumal aus dem angefochtenen Urteil nicht hervorgeht, dass die Kündigung der Wohnung die Unmöglichkeit bewirkt hatte, den Kläger zur Arbeit abzurufen. Ob anders zu entscheiden wäre, wenn die von der Beklagten angeführte mündliche Äusserung des Verwaltungsdirektors nachgewiesen wäre, erscheint fraglich, kann aber offen bleiben. Jedenfalls ist nicht ersichtlich, woraus der Kläger zweifelsfrei auf einen Verzicht der Beklagten auf seine Arbeitsbereitschaft hätte schliessen müssen. Auch in dieser Hinsicht hält das angefochtene Urteil vor Bundesrecht stand.
7. Aus diesen Gründen sind sowohl die Berufung als auch die Anschlussberufung als unbegründet abzuweisen.
Dem Verfahrensausgang entsprechend sind die Kosten des bundesgerichtlichen Verfahrens zu 2/3 dem Kläger und zu 1/3 der Beklagten aufzuerlegen. Der Kläger hat der Beklagten für das bundesgerichtliche Verfahren eine reduzierte Parteientschädigung auszurichten (Art. 156 Abs. 3 OG und Art. 159 Abs. 3 OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Berufung und die Anschlussberufung werden abgewiesen.
1. Die Berufung und die Anschlussberufung werden abgewiesen.
2. Die Gerichtsgebühr von Fr. 7'000.-- wird zu 2/3 dem Kläger und zu 1/3 der Beklagten auferlegt.
2. Die Gerichtsgebühr von Fr. 7'000.-- wird zu 2/3 dem Kläger und zu 1/3 der Beklagten auferlegt.
3. Der Kläger hat der Beklagten für das bundesgerichtliche Verfahren eine reduzierte Entschädigung von Fr. 2'700.-- zu bezahlen.
3. Der Kläger hat der Beklagten für das bundesgerichtliche Verfahren eine reduzierte Entschädigung von Fr. 2'700.-- zu bezahlen.
4. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell A.Rh., 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 14. September 2004
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: