Sachverhalt:
A. S._ arbeitete seit Februar 1983 in unterschiedlichen Funktionen bei der Eidgenössischen Verwaltung X._, seit Juli 1999 im Bereich Aussendienst. Dort wurde er im Zusammenhang mit einer Reorganisation der Eidgenössischen Verwaltung X._ im August 2006 mit den Aufgaben als Aussendienstkoordinator betraut. Anfangs Dezember 2009 unterbreitete die Eidgenössische Verwaltung X._ als Arbeitgeberin S._ als Arbeitnehmer eine Vereinbarung im Sinne von Art. 4 Abs. 2 der Verordnung vom 10. Juni 2004 über die Stellen- und Personalbewirtschaftung im Rahmen von Entlastungsprogrammen und Reorganisationen (Reorganisationsverordnung, SR 172.220.111.5), welche Letzterer am 7. Dezember 2009 unterzeichnete. Ziff. 9 dieser Vereinbarung sah vor, dass der Arbeitsvertrag gestützt auf Art. 12 Abs. 6 lit. e BPG gekündigt werde, sofern der Arbeitnehmer nicht innerhalb von sechs Monaten nach Unterzeichnung eine andere zumutbare Arbeit finden werde. Mit Verfügung vom 29. Juni 2010 löste die Eidgenössische Verwaltung X._ das Arbeitsverhältnis mit S._ per 31. Dezember 2010 auf, da seine Stelle reorganisationsbedingt aufgehoben worden sei und ihm trotz Vermittlungsbemühungen keine andere zumutbare Stelle habe angeboten werden können.
Am 20. Juli 2010 machte S._ einerseits bei der Eidgenössischen Verwaltung X._ die Nichtigkeit der Kündigungsverfügung vom 29. Juni 2010 geltend und erhob andererseits dagegen beim Eidgenössischen Finanzdepartement (EFD) Beschwerde. Das EFD wies am 20. Dezember 2010 die Beschwerde ab, stellte die Gültigkeit der Kündigung der Eidgenössischen Verwaltung X._ vom 29. Juni 2010 fest und entzog einer allfälligen Beschwerde die aufschiebende Wirkung.
B. Gegen diesen Entscheid erhob S._ am 27. Januar 2011 Beschwerde beim Bundesverwaltungsgericht. Dieses hiess am 11. Juli 2011 die Beschwerde im Sinne der Erwägungen gut, hob den Entscheid des EFD vom 20. Dezember 2010 auf und stellte die Nichtigkeit der Kündigung vom 29. Juni 2010 fest.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die Schweizerische Eidgenossenschaft (nachfolgend Beschwerdeführerin) Aufhebung des Urteils des Bundesverwaltungsgerichts vom 11. Juli 2011 und Bestätigung des Entscheids des EFD vom 20. Dezember 2010, eventualiter Aufhebung der Kündigung vom 29. Juni 2010 und Rückweisung der Angelegenheit zur Berechnung einer allfälligen Entschädigung im Sinne von Art. 19 BPG.
S._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Gegen den angefochtenen Entscheid steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>). Die übrigen Voraussetzungen für das Eintreten auf die Beschwerde sind ebenfalls erfüllt.
1.2 Mit der Beschwerde kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Beschwerdeführerin macht geltend, die Vorinstanz habe Bestimmungen des Bundespersonalrechts verletzt.
1.3 Grundsätzlich wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann unter Berücksichtigung der den Parteien obliegenden Begründungs- resp. Rügepflicht eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.2 S. 252 mit Hinweisen, 369 E. 2 S. 371; <ref-ruling> E. 1.4.1 S. 254). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1, Art. 105 Abs. 2 BGG).
2. Strittig ist, ob das Bundesverwaltungsgericht die mit Entscheid des EFD vom 20. Dezember 2010 bestätigte Kündigung der Eidgenössischen Verwaltung X._ vom 29. Juni 2010 zu Recht für nichtig erklärt hat.
3. Das Bundespersonalgesetz erlaubt die ordentliche Kündigung durch den Arbeitgeber aus schwer wiegenden wirtschaftlichen oder betrieblichen Gründen, sofern der Arbeitgeber der betroffenen Person keine zumutbare andere Arbeit anbieten kann (Art. 12 Abs. 6 lit. e BPG). Die Vorinstanz ging davon aus, dass S._ aus schwer wiegenden wirtschaftlichen bzw. betrieblichen Gründen gemäss Art. 12 Abs. 6 lit. e BPG gekündigt wurde. Dies blieb unbestritten.
4. 4.1 Die speziell für den Stellenabbau in der Bundesverwaltung erlassene, wiederholt in der befristeten Geltungsdauer verlängerte Verordnung vom 10. Juni 2004 über die Stellen- und Personalbewirtschaftung im Rahmen von Entlastungsprogrammen und Reorganisationen bezweckt, den Stellenabbau möglichst ohne Entlassungen sozialverträglich und ökonomisch umzusetzen (Art. 1 Abs. 1 Reorganisationsverordnung). In Art. 4 dieser Verordnung ist das Verfahren geregelt, wie mit betroffenen Angestellten umzugehen ist (Urteil 1C_361/2007 vom 17. Juni 2008 E. 3).
4.2 Gemäss Art. 4 Abs. 1 der Reorganisationsverordnung müssen Angestellte, die voraussichtlich nicht mehr in der Verwaltungseinheit beschäftigt werden können, spätestens sechs Monate vor einer allfälligen Kündigung schriftlich darüber informiert werden. Die Verwaltungseinheit schliesst mit der angestellten Person eine Vereinbarung ab. Darin verpflichtet sich der oder die Angestellte, aktiv an der Suche nach einer Stelle mitzuwirken und eine zumutbare andere Arbeit anzunehmen. Die Arbeitgeberin verpflichtet sich, "das Möglichste" zu tun, um der angestellten Person innerhalb oder gegebenenfalls ausserhalb der Bundesverwaltung eine zumutbare andere Arbeit zu vermitteln und wenn möglich die Kündigung zu vermeiden (Art. 4 Abs. 2 der Reorganisationsverordnung). Nach Abschluss der Vereinbarung wird die angestellte Person in einer Job-Datenbank erfasst. Die Arbeitgeberin, unterstützt durch das Job-Center (Art. 6 der Reorganisationsverordnung), und die angestellte Person suchen intensiv nach einer internen oder externen Stelle (Art. 4 Abs. 4 der Reorganisationsverordnung). Gemäss Art. 4 Abs. 7 der Reorganisationsverordnung wird das Arbeitsverhältnis aus Gründen nach Art. 12 Abs. 6 Bst. e BPG aufgelöst, wenn innerhalb von sechs Monaten nach Unterzeichnung der Vereinbarung keine andere zumutbare Arbeit gefunden werden konnte.
5. 5.1 Das Bundesverwaltungsgericht hat die Kündigung vom 29. Juni 2010 für nichtig erklärt. Es hat zwar die erste Tatbestandsvoraussetzung von Art. 12 Abs. 6 lit. e BPG - nämlich: schwer wiegende wirtschaftliche oder betriebliche Gründe - bejaht und sodann erkannt, dass die Arbeitgeberin den Vorgaben von Art. 4 Abs. 4 und Abs. 7 der Reorganisationsverordnung entsprochen habe. Es kam jedoch zum Schluss, der Arbeitgeberin sei der Nachweis nicht gelungen, dass sie mit einer beschränkten Anzahl von anderen Arbeitgebern nach Art. 3 BPG Kontakt aufgenommen habe, um nach Möglichkeit eine andere zumutbare Stelle zu finden. Es sei daher nicht erwiesen, dass die Arbeitgeberin dem Beschwerdegegner keine zumutbare andere Arbeit im Sinne der zweiten Tatbestandsvoraussetzung von Art. 12 Abs. 6 lit. e BPG habe anbieten können. Demzufolge sei die Kündigung nichtig, das Arbeitsverhältnis damit gemäss Art. 14 Abs. 1 BPG nicht beendet und der Beschwerdegegner weiter zu beschäftigen.
5.2 Demgegenüber macht die Beschwerdeführerin geltend, sie habe die bei einer Kündigung nach Art. 12 Abs. 6 lit. e BPG beachtlichen bundesrechtlichen Vorschriften eingehalten und das Möglichste unternommen, um dem Beschwerdegegner eine andere zumutbare Arbeit zu vermitteln. Insbesondere bestreitet sie, dass ihr im Rahmen der Vermittlungsbemühungen eine Verpflichtung zur direkten Kontaktaufnahme mit potentiellen Arbeitgebern obliege. Bestehe keine solche Verpflichtung, sei die vorinstanzliche Nichtigerklärung der Kündigung vom 29. Juni 2010 wegen Bundesrechtswidrigkeit aufzuheben.
5.3 Der Beschwerdegegner macht geltend, es gehe nicht um eine Verpflichtung zu Blindbewerbungen bei andern internen Arbeitgebern. Es hätte andere Möglichkeiten gegeben, ihn aktiv zu unterstützen. Vorab hätte die Arbeitgeberin selbst die Job-Datenbank konsultieren und mögliche Arbeitsplätze mit ihm anschauen können, um sich anschliessend mit den fraglichen Anstellungsverantwortlichen in Verbindung zu setzen und ihn für die Stelle zu empfehlen; oder die eigene Personalabteilung der Eidgenössischen Verwaltung X._ beziehungsweise des EFD hätte beauftragt werden können, ihm eine oder mehrere geeignete Stellen zu suchen, um sie ihm für die Bewerbung vorzuschlagen; oder er hätte von der Arbeitgeberin beauftragt werden können, passende Stellenangebote selber zu suchen, damit sich die Verantwortlichen der Eidgenössischen Verwaltung X._ anschliessend dort aktiv für ihn hätten einsetzen können. Es sei auch anzunehmen, dass die Personalverantwortlichen der verschiedenen Ämter und Departemente periodisch Konferenzen durchführten, anlässlich welcher sein Fall hätte thematisiert werden können.
6. Nachfolgend zu prüfen ist, ob das zweite Tatbestandselement des Art. 12 Abs. 6 lit. e BPG - der Nachweis des Arbeitgebers, der betroffenen Person keine zumutbare andere Arbeit anbieten zu können - erfüllt ist.
6.1 Diesbezüglich hielt die Vorinstanz unter zutreffendem Hinweis auf das Urteil 1C_361/2007 vom 17. Juni 2008 fest, dass die Arbeitgeberin ihre Verpflichtungen nicht verletzte, indem sie dem Beschwerdegegner während der vereinbarten sechsmonatigen Frist keine Stelle innerhalb der Eidgenössischen Verwaltung X._ anbot. Eine solche Verpflichtung bestehe nur insoweit, als eine geeignete Stelle überhaupt existiere. Weiter anerkannte das Bundesverwaltungsgericht, dass die Beschwerdeführerin verschiedene, von der Reorganisationsverordnung vorgesehene Massnahmen getroffen hatte. Es steht jedoch unbestritten fest, dass die Eidgenössische Verwaltung X._ innerhalb der Bundesverwaltung nicht in direkten Kontakt mit anderen Arbeitgebern im Sinne von Art. 3 BPG trat, um dem Beschwerdegegner eine zumutbare andere Arbeit zu vermitteln.
6.2 Wie das Bundesverwaltungsgericht korrekt ausgeführt hat, sieht Art. 19 Abs. 1 BPG vor, dass die Arbeitgeberin alle sinnvollen Möglichkeiten einer zumutbaren Weiterbeschäftigung auszuschöpfen hat, bevor sie Angestellten ohne deren Verschulden kündigt. Nach Art. 31 Abs. 3 BPG können die Ausführungsbestimmungen Massnahmen und Leistungen zur Milderung der Folgen sozialer Härten vorsehen.
In Art. 104 BPV hat der Bundesrat Massnahmen für die sozialverträgliche Umsetzung von Umstrukturierungen definiert. Gegenüber der Auflösung des Arbeitsverhältnisses haben nach dieser Bestimmung folgende Massnahmen Vorrang (Art. 104 Abs. 2 BPV): Die Weiterbeschäftigung der Angestellten auf einer anderen Stelle bei einem Arbeitgeber nach Art. 3 BPG (Bst. a), die Vermittlung von Stellen ausserhalb der Bundesverwaltung an von der Entlassung bedrohte Angestellte (Bst. b), die Umschulung und Weiterbildung (Bst. c) sowie die vorzeitige Pensionierung (Bst. d). Die Angestellten unterstützen die Bemühungen der Arbeitgeberin. Sie arbeiten aktiv an den eingeleiteten Massnahmen mit und entwickeln Eigeninitiative, insbesondere bei der Suche nach einer neuen Anstellung (Art. 104 Abs. 4 BPV).
6.3 "Das Möglichste" im Sinne von Art. 4 Abs. 2 Satz 3 der Reorganisationsverordnung (vgl. dazu bereits E. 4.2 hievor) erfasst nach dem Wortlaut alle nur denkbaren Massnahmen. Der Gesetzgeber bezweckte mit Art. 19 Abs. 1 BPG eine Verpflichtung des Arbeitgebers, "alle sinnvollen und zumutbaren Möglichkeiten der Weiterbeschäftigung zu prüfen und auszuschöpfen" (Botschaft zum Bundespersonalgesetz vom 14. Dezember 1998, BBl 1999, S. 1597 ff., S. 1618). Die Verpflichtung der Arbeitgeberin gemäss Satz 3 von Art. 4 Abs. 2 der Reorganisationsverordnung geht jedenfalls, wie die Vorinstanz mit angefochtenem Entscheid (S. 13 f.) sinngemäss zutreffend zum Ausdruck brachte, über die in Art. 4 (insbesondere Abs. 4) der Reorganisationsverordnung beispielhaft genannten Unterstützungsmassnahmen hinaus.
6.4 Die Beschwerdeführerin macht nicht geltend, dass der Beschwerdegegner seine arbeitsvertraglichen Pflichten verletzt habe, ihn an der Auflösung des Arbeitsverhältnisses ein Verschulden treffe, oder das Vertrauensverhältnis in irgendeiner Form belastet gewesen sei. Unter den gegebenen Umständen ist angesichts der seitens der Beschwerdeführerin unbestritten unterlassenen Kontaktaufnahmen zu anderen Arbeitgebern innerhalb der Bundesverwaltung sowie unter Berücksichtigung der tatsächlich geleisteten Unterstützungsmassnahmen der Eidgenössischen Verwaltung X._ jedenfalls nicht als bundesrechtswidrig zu beanstanden, dass das Bundesverwaltungsgericht auf Beweislosigkeit schloss, soweit der Bund als Arbeitgeber hinsichtlich der Suche nach einem neuen Arbeitsplatz für den 27 Jahre lang im Dienst der Arbeitgeberin tätig gewesenen Beschwerdegegner dazu verpflichtet war, "das Möglichste" zu tun, um Letzterem eine zumutbare andere Arbeit zu vermitteln.
6.5 Fehlt es hier somit am Nachweis der genügenden Bemühungen, dem Beschwerdegegner eine andere zumutbare Arbeitsstelle zu vermitteln, sind nicht alle Tatbestandsvoraussetzungen des Art. 12 Abs. 6 lit. e BPG belegt und demzufolge der entsprechende Kündigungsgrund nicht erfüllt. Wie das Bundesverwaltungsgericht zutreffend erkannte, ist demach die Kündigung nach Art. 12 Abs. 6 BPG nicht begründet und folglich nichtig im Sinne von Art. 14 Abs. 1 lit. b BPG. Was die Beschwerdeführerin im Übrigen hiegegen vorbringt, ist unbegründet. Es sind aktenkundig keine entsprechenden Anhaltspunkte ersichtlich und wird auch nicht substantiiert dargelegt, dass der Beschwerdegegner seine Mitwirkungspflicht hinsichtlich einer aktiven Stellensuche (vgl. Art. 4 Abs. 2 Reorganisationsverordnung) verletzt hätte.
7. Was die Beschwerdeführerin schliesslich gegen die Weiterbeschäftigungsfolge der Nichtigkeitsfeststellung in Bezug auf die hier strittige Kündigung vorbringt, ist nicht stichhaltig.
7.1 Nach Sinn und Zweck von Art. 14 Abs. 1 und 2 BPG vermag eine im Sinne dieser Bestimmungen nichtige Kündigung ein Arbeitsverhältnis grundsätzlich nicht zu beenden, sondern hat die Weiterbeschäftigung der betroffenen Person zur Folge (Urteil 8C_808/2010 vom 28. Juni 2011 E. 5.2; HARRY NÖTZLI, Die Beendigung von Arbeitsverhältnissen im Bundespersonalrecht, Bern 2005, Rz. 325). Vorbehalten bleibt indessen die Entschädigung nach Art. 19 BPG (Art. 14 Abs. 5 BPG). Stellt eine Beschwerdeinstanz die Nichtigkeit einer Kündigung im Sinne von Art. 14 Abs. 1 und 2 BPG fest, kommt das Ausrichten einer Entschädigung anstelle der Weiterbeschäftigung grundsätzlich nur subsidiär in Frage. Für den Beschwerdegegner stand von seinen Fähigkeiten her und auf Grund seiner langjährigen verwaltungsinternen Arbeitserfahrung in verschiedenen Funktionen der Eidgenössischen Verwaltung X._ grundsätzlich eine breite Auswahl an alternativen Weiterbeschäftigungsmöglichkeiten bei Arbeitgebern nach Art. 3 BPG zur Verfügung. Zudem hat der Beschwerdegegner - abweichend vom Sachverhalt, welcher dem Urteil 1C_277/2007 vom 30. Juni 2008 zugrunde lag - keinen Kündigungsgrund gesetzt. Schliesslich spricht auch der reorganisationsbedingte Wegfall der bisherigen Arbeitsstelle des Beschwerdegegners in der Eidgenössischen Verwaltung X._ nicht gegen die Aufhebung der Kündigung und Weiterbeschäftigung bei einem Arbeitgeber nach Art. 3 BPG.
7.2 Fehlt es am Nachweis der genügenden Bemühungen, dem Beschwerdegegner eine andere zumutbare Arbeitsstelle bei Arbeitgebern nach Art. 3 BPG ausserhalb der von der Reorganisation betroffenen Eidgenössischen Verwaltung X._ zu vermitteln (vgl. E. 6.5 hievor), und legt die Beschwerdeführerin nicht dar, dass die gegebenen Umstände hinsichtlich der reorganisationsbedingt ausgesprochenen Kündigung eine Ausnahme von der Weiterbeschäftigungspflicht des Arbeitgebers zu rechtfertigen vermöchten, bleibt es bei der Rechtsfolge gemäss angefochtenem Entscheid, wonach das Arbeitsverhältnis basierend auf dem Grundsatz von Art. 14 BPG fortbesteht. Mithin liegt angesichts des Versäumnisses der Arbeitgeberin, nicht das Möglichste zur Vermittlung einer anderen zumutbaren Arbeitsstelle getan zu haben (vgl. Art. 4 Abs. 2 der Reorganisationsverordnung), kein Ausnahmefall vor, in welchem an die Stelle der Weiterbeschäftigungspflicht des Arbeitgebers der Entschädigungsanspruch des Arbeitnehmers treten kann (vgl. Art. 19 Abs. 3 BPG), zumal der Beschwerdegegner - unter Umständen gerade als Folge der mangelhaften Vermittlungsbemühungen, jedenfalls aber unbestritten ohne dessen Verschulden - nicht bei einem Arbeitgeber nach Art. 3 BPG weiterbeschäftigt wird.
8.1 8.1.1 Das Verfahren ist kostenpflichtig (Art. 65 f. BGG). Nach <ref-law> 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 (<ref-law>).
8.1.2 Das Bundesgericht hat erkannt, dass kein sachlicher Grund ersichtlich ist, der es rechtfertigen würde, bezüglich eines als Arbeitgeber in seinen Vermögensinteressen betroffenen Gemeinwesens von der Auferlegung von Gerichtskosten abzusehen (<ref-ruling> E. 8.1.4 S. 41 mit Hinweisen). Dies trifft auch hier auf die in ihrem amtlichen Wirkungskreis handelnde Schweizerische Eidgenossenschaft zu. Da die Voraussetzungen des Ausnahmetatbestandes von <ref-law> nicht erfüllt sind, hat die unterliegende Beschwerdeführerin die Gerichtskosten zu tragen (<ref-law>).
8.2 Die Beschwerdeführerin hat dem Beschwerdegegner zudem eine Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Bundesverwaltungsgericht, Abteilung I, schriftlich mitgeteilt.
Luzern, 1. Mai 2012
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Der Gerichtsschreiber: Hochuli