Sachverhalt:
A. X._ erteilte als stellvertretender Honorarkonsul in Maskat (Oman) im Zeitraum von September 1999 bis Oktober 2003 134 bangladeschischen Staatsangehörigen ein Visum für die Einreise in die Schweiz. Dabei täuschte er durch Anfertigung fiktiver Anträge und weiterer Dokumente vor, die Visa seien für 134 omanische Staatsbürger, für die keine Visumsbeschränkungen bestanden, ausgestellt worden. Die echten Visaanträge der 134 bangladeschischen Staatsangehörigen sowie allfällige Beilagen vernichtete er, nachdem er von der erfolgten Einreise der fraglichen Personen in die Schweiz erfahren hatte. Für die Erteilung der Visa nahm er insgesamt 60'300 omanische Rial (entspricht 211'050 Schweizer Franken) entgegen.
B. Im Wesentlichen gestützt auf diesen Sachverhalt sprach das Bundesstrafgericht X._ am 28. November 2005 der mehrfachen Urkundenfälschung im Amt und der Vorteilsannahme schuldig und bestrafte ihn mit neun Monaten Gefängnis unter Gewährung des bedingten Strafvollzugs. Von der Anklage der mehrfachen Urkundenfälschung im Amt hinsichtlich der Einträge in das Visumsregister in 134 Fällen, der mehrfachen Unterdrückung von Urkunden, des mehrfachen Sich-Bestechen-Lassens hinsichtlich zweier 1998 erteilter Visa sowie 27 weiterer Visa und der mehrfachen Widerhandlung gegen das ANAG sprach es ihn frei. Auf die Anklage des mehrfachen Sich-Bestechen-Lassens hinsichtlich der Erteilung von 134 Visa trat es nicht ein.
C. Die Schweizerische Bundesanwaltschaft erhebt gegen das Urteil des Bundesstrafgerichts Nichtigkeitsbeschwerde beim Bundesgericht. Sie beantragt, es sei der angefochtene Entscheid aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
D. Das Bundesstrafgericht ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Beschwerdegegner beantragt in seiner Vernehmlassung sinngemäss die Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. Die Beschwerde richtet sich zunächst gegen den Freispruch von der Anklage der mehrfachen Unterdrückung von Urkunden im Sinne von Art. 254 Abs. 1 StGB. Die Beschwerdeführerin rügt, die Vorinstanz verneine zu Unrecht die Strafbarkeit der Vernichtung der 134 Visaantragsformulare gemäss omanischem Recht und damit die Strafbarkeit in der Schweiz nach Art. 16 Abs. 2 VG.
Nach Art. 269 StGB kann mit Nichtigkeitsbeschwerde nur die Verletzung eidgenössischen Rechts geltend gemacht werden. Ausländisches Recht wird vom Bundesgericht dagegen nicht überprüft (<ref-ruling> E. 7c S. 87). Die Beschwerdeführerin macht allein geltend, die Visaformulare stellten nach omanischem Recht Urkunden dar, deren Vernichtung strafbar sei. Das Erfordernis der beidseitigen Strafbarkeit sei daher erfüllt. Da demnach einzig die Verletzung ausländischen Rechts gerügt wird, ist auf die Beschwerde in diesem Punkt nicht einzutreten.
2. Die Vorinstanz tritt auf die Anklage des Sich-Bestechen-Lassens im Zusammenhang mit der Erteilung von 134 Visa an bangladeschische Staatsangehörige nicht ein, weil in der Anklageschrift die Amtshandlung, auf die sich der Vorteil beziehen müsse, nicht genügend umschrieben werde. Die Beschwerdeführerin stellt sich auf den Standpunkt, diese Auffassung beruhe auf einer unzutreffenden Anwendung von Art. 126 BStP, insbesondere von Abs. 1 Ziff. 2.
2.1 Die Nichtigkeitsbeschwerde an den Kassationshof des Bundesgerichtes kann sich nur gegen letztinstanzliche Urteile richten (Art. 33 Abs. 3 lit. b SGG i.V.m. Art. 268 BStP). Mit dem Nichteintreten ist über den Vorwurf der passiven Bestechung in 134 Fällen für das vorliegende Verfahren endgültig entschieden. Entgegen der vorinstanzlichen Vernehmlassung liegt ein Endentscheid im Sinne von Art. 268 BStP vor, weshalb auf die Beschwerde einzutreten ist.
2.1 Die Nichtigkeitsbeschwerde an den Kassationshof des Bundesgerichtes kann sich nur gegen letztinstanzliche Urteile richten (Art. 33 Abs. 3 lit. b SGG i.V.m. Art. 268 BStP). Mit dem Nichteintreten ist über den Vorwurf der passiven Bestechung in 134 Fällen für das vorliegende Verfahren endgültig entschieden. Entgegen der vorinstanzlichen Vernehmlassung liegt ein Endentscheid im Sinne von Art. 268 BStP vor, weshalb auf die Beschwerde einzutreten ist.
2.2 2.2.1 Die Anklageschrift bezeichnet das strafbare Verhalten, dessen der Angeklagte beschuldigt wird, nach seinen tatsächlichen und gesetzlichen Merkmalen (Art. 126 Abs. 1 Ziff. 2 BStP). Im Zuge des Erlasses des Strafgerichtsgesetzes wurden Art. 126 BStP zum notwendigen Anklageinhalt und Art. 127 BStP zur Zustellung der Anklage angepasst beibehalten, die übrigen Bestimmungen zum Anklagezulassungsverfahren indessen gestrichen (Art. 128-134 BStP; vgl. Anhang Ziff. 9 des Strafgerichtsgesetzes vom 4. Okt. 2002, SGG, SR 173.71). Begründet wurde diese Streichung mit der Umständlichkeit des zweistufigen Verfahrens. Zudem stelle der Entscheid der Anklagekammer über die Anklagezulassung eine Art "Vor-Urteil" dar (Botschaft, BBl 2001, 4255). Unter altem Recht hatte die Anklagekammer im Rahmen der ihr obliegenden formellen Prüfung insbesondere darüber zu befinden, ob die Anklageschrift den aufgrund des Akkusationsprinzips an sie zu stellenden Anforderungen entsprach (<ref-ruling>, E. 1 b). Gemäss diesem Entscheid kam der Anklagekammer ferner die Kompetenz zu, eine fehlerhafte Anklageschrift an den Bundesanwalt zurückzuweisen (BGE a.a.O. E. 1 c.dd). Auch der Entwurf zu einer vereinheitlichten eidgenössischen Strafprozessordnung sieht vor, dass die Verfahrensleitung die Anklageschrift überprüft. Ergibt sich auf Grund dieser Prüfung oder später im Verfahren, dass ein Urteil einstweilen nicht ergehen kann, so sistiert das Gericht das Verfahren. Falls erforderlich, weist es die Anklage zur Ergänzung oder Berichtigung an die Staatsanwaltschaft zurück (Art. 330 E-StPO, BBl 2006 1389, 1491; dazu Botschaft, BBl 2006 1275 ff.).
2.2.2 Es stellt sich die Frage, wie unter geltendem Recht bis zum Inkrafttreten der vereinheitlichten Strafprozessordnung bei mangelhaften Anklagen zu verfahren ist. Aus dem Umstand, dass nach dem Wegfall des Anklagezulassungsverfahrens keine separate Behörde mehr über die Anklagezulassung befindet, folgt nicht, dass bei mangelhaften Anklagen lediglich die Möglichkeit bleibt, im Endentscheid nicht darauf einzutreten. Vielmehr sind Anklagemängel wie bisher während des Verfahrens zu beheben. Nach Armand Meyer, Die Bindung des Strafrichters an die eingeklagte Tat, Diss. Zürich 1972, S. 165 f., verliert der Ankläger ab einem gewissen Zeitpunkt die Herrschaft über die Anklage. Das Gericht hat dann nur noch die Möglichkeit entweder zu verurteilen oder freizusprechen (Art. 168 Abs. 2 BStP). Genügt die Anklage nicht, so muss grundsätzlich freigesprochen werden. Ein solcher Freispruch ist sehr unbefriedigend, wenn sich der Angeklagte nach dem Untersuchungsergebnis eindeutig schuldig gemacht hat. Um dem Dilemma zwischen Verletzung des Anklageprinzips und ungerechtfertigtem Freispruch zu entgehen, bietet sich - zumindest dort wo ein Anklagezulassungsverfahren fehlt - die Rückweisung der Anklageschrift zur Berichtigung an (vgl. auch Edgar Frey, Die Anklage im schweizerischen Strafprozessrecht, Diss. Zürich 1946, S. 76 ff.; M. Guldener, Klage- und Anklageänderung (...), in: FS-Pfenninger, Zürich 1956, S. 84 ff.; Niklaus Schmid, in: Andreas Donatsch/ Niklaus Schmid (Hrsg.), Kommentar zur Strafprozessordnung des Kantons Zürich, Zürich 1996, § 182 N 18). Auch der Bundesanwalt hat Möglichkeiten zur Anklageberichtigung während des Verfahrens (Art. 166 BStP). Mangelhafte Anklagen sind deshalb an die Bundesanwaltschaft zur Verbesserung zurückzuweisen.
2.2.3 Die Vorinstanz gelangt zum Schluss, die Anklageschrift sei hinsichtlich der Amtshandlung, auf die sich der Vorteil beziehen müsse, ungenügend, was eine materielle Beurteilung des Vorwurfs ausschliesse. Im Endurteil tritt sie deshalb in diesem Punkt nicht auf die Anklage ein und verweist in ihrer Vernehmlassung auf die Möglichkeit der Wiedereinbringung. Dieses Vorgehen erweist sich als nicht bundesrechtskonform. Beinhaltet die Anklage nicht alle objektiven Tatbestandsmerkmale des angeklagten Delikts, so ist die Anklageschrift nach dem Gesagten zur Ergänzung an die Bundesanwaltschaft zurückzuweisen. Es geht nicht an, im Endentscheid auf die Anklage nicht einzutreten unter Hinweis auf die Möglichkeit der Wiedereinbringung, da der Angeklagte für den Fall, dass keine erneute Anklage erhoben wird, über die mit der ursprünglichen Anklage öffentlich gegen ihn erhobenen Anschuldigungen im Ungewissen gelassen würde. Wie erwähnt hat er jedoch einen grundsätzlichen Anspruch darauf, vom Gericht freigesprochen oder verurteilt zu werden (Art. 168 Abs. 2 BStP; s.a. Arthur Bauhofer, Wer vor Gericht gestellt wird, muss freigesprochen oder verurteilt werden, in: FS-Pfenninger, Zürich 1956, S. 15 ff.; Robert Hauser/Erhard Schweri/Karl Hartmann, Schweizerisches Strafprozessrecht, 6. Aufl., § 50 N 8a; Schmid, a.a.O. § 182 N 1). Ferner gebieten auch der Grundsatz der materiellen Wahrheitsfindung (Art. 146 Abs. 2 BStP; s.a. Obergericht Zürich, I. Strafkammer, Urteil vom 10. Mai 1984, ZR 84/1985 Nr. 22 S. 66), das Prinzip der Verfahrenseinheit sowie die Prozessökonomie, den Anklagesachverhalt nach Möglichkeit in einem Verfahren zu beurteilen. Anklagemängel sind darum umgehend zu beheben, um über die berichtigte Anklage im selben Verfahren definitiv entscheiden zu können. Aus diesen Gründen ist der vorinstanzliche Nichteintretensentscheid aufzuheben. Vor der neuerlichen Beurteilung wird die Vorinstanz der Beschwerdeführerin Gelegenheit zur Anklageergänzung einzuräumen haben. Es braucht an dieser Stelle deshalb auch nicht entschieden zu werden, ob die Anklage im vorliegenden Fall den Anforderungen von Art. 126 BStP entsprach.
3. 3.1 Der Freispruch von der Anklage der Widerhandlung gegen das ANAG beruht nach Ansicht der Beschwerdeführerin auf einer offensichtlich unrichtigen und unvollständigen Sachverhaltsfeststellung. Das Bundesstrafgericht bestreitet in seinen Gegenbemerkungen, dass die Bundesanwaltschaft Willkür in der Beweiswürdigung rügen könne. Art. 9 BV gehöre zu den Individualrechten, weshalb sich eine Behörde nach ständiger Praxis nicht darauf berufen könne.
3.2 Das Bundesstrafgericht beurteilt erstinstanzlich Straffälle, die das Gesetz der Gerichtsbarkeit des Bundes zuweist (Art. 191a Abs. 1 BV; Art. 1 Abs. 1 des Bundesgesetzes über das Bundesstrafgericht, Strafgerichtsgesetz, SGG; SR 173.71). Gegen Entscheide von dessen Strafkammer kann beim Kassationshof des Bundesgerichts Nichtigkeitsbeschwerde geführt werden. Das Verfahren richtet sich nach Art. 268-278bis BStP, Art. 269 Abs. 2 BStP findet jedoch keine Anwendung. Der Bundesanwalt ist zur Beschwerde berechtigt (Art. 33 Abs. 3 lit. b SGG). Art. 269 Abs. 2 BStP, welcher bei Nichtigkeitsbeschwerden gegen kantonale Urteile die staatsrechtliche Beschwerde vorbehält, findet lediglich deshalb keine Anwendung, weil die staatsrechtliche Beschwerde sich nicht gegen Entscheide von Bundesinstanzen richten kann (Art. 84 ff. OG). Im Übrigen bestehen jedoch gegen Entscheide des Bundesstrafgerichts die gleichen Beschwerdemöglichkeiten wie gegen kantonale Strafurteile. Nach der Rechtsprechung kann der Angeklagte deshalb in der Nichtigkeitsbeschwerde gegen Bundesstrafgerichtsentscheide Verfassungs- und insbesondere auch Willkürrügen erheben (Entscheid 6S.293/2005 vom 24. Februar 2006, E. 2.1). Die öffentliche Anklägerin andererseits ist nach ständiger Rechtsprechung nicht zur Ergreifung staatsrechtlicher Beschwerden gegen kantonale Entscheide berechtigt. Die staatsrechtliche Beschwerde ist das Rechtsmittel des Bürgers, um sich gegen die Verletzung seiner verfassungsmässigen Rechte durch den Staat zur Wehr zu setzen (Art. 84 Abs. 1 lit. a und Art. 88 OG). Als Trägerin der Hoheitsgewalt steht der öffentlichen Anklägerin dieses Rechtsmittel nicht offen (<ref-ruling> E. 2a; <ref-ruling> E. 1a; 48 I 106). Nach geltendem Recht kann die Bundesanwaltschaft deshalb in der Beschwerde gegen Bundesstrafgerichtsentscheide keine Verfassungsrügen erheben. Es ist nicht ersichtlich, dass der Gesetzgeber in Art. 33 Abs. 3 lit. b SGG die Beschwerdebefugnis der Bundesanwaltschaft in diesem Sinne hätte erweitern wollen, zumal diese übergangsrechtliche Norm im bundesrätlichen Entwurf noch nicht figurierte und sie vom Parlament diskussionslos angenommen wurde (vgl. BBl 2001 4517 ff.; Amtl. Bull. SR 2001 S. 920, Sitzung vom 6. Dezember 2001; Amtl. Bull. NR 2002 S. 1215, Sitzung vom 17. September 2002). Auf die Beschwerde ist daher nicht einzutreten, soweit sie sich gegen die vorinstanzlichen Sachverhaltsfeststellungen im Zusammenhang mit der Widerhandlung gegen das ANAG wendet.
3.3 Anzumerken bleibt, dass damit die Grundsatzfrage, ob die Bundesanwaltschaft Verfassungsrügen erheben kann, nur für das Übergangsrecht nach Art. 33 Abs. 3 SGG entschieden ist. Weil die Übergangsbestimmungen vor der Beratung des Bundesgerichtsgesetzes verabschiedet wurden, sind die Rügemöglichkeiten der Bundesanwaltschaft nach der künftigen Beschwerde in Strafsachen mit dem vorliegenden Entscheid nicht präjudiziert.
4. Die Beschwerdeführerin rügt weiter, dass die Einreise der bangladeschischen Staatsangehörigen, denen der Beschwerdegegner ein Visum erteilte, auch deshalb rechtswidrig gewesen sei, weil sie generell die Voraussetzungen für die Visumserteilung nicht erfüllt hätten. Mit dieser Kritik weicht die Beschwerdeführerin vom verbindlich festgestellten Sachverhalt ab, was im Rahmen der Nichtigkeitsbeschwerde unzulässig ist (Art. 273 Abs. 1 lit. b BStP). Die Vorinstanz trifft gar keine Feststellungen zur Frage, ob die bangladeschischen Bürger, die in den Genuss eines Visums gelangten, die persönlichen Anforderungen dafür erfüllten, weil sie der Ansicht ist, dass die Anklageschrift gar keinen entsprechenden Vorwurf enthält. Für den Fall, dass die Vorinstanz in ihrem neuerlichen Entscheid auf eine diesbezüglich ergänzte Anklage eintreten sollte, wird sie sich zu diesem Einwand äussern müssen.
5. Die gegen die Strafzumessung vorgebrachten Rügen betreffen allein die Feststellung des Sachverhalts. Wie bereits dargelegt wurde (E. 3), ist die Beschwerdeführerin nicht legitimiert, solche Einwände zu erheben.
6. Aus diesen Gründen ist die Nichtigkeitsbeschwerde gutzuheissen, soweit auf sie eingetreten werden kann. Bei diesem Verfahrensausgang trägt der Beschwerdegegner die Kosten des bundesgerichtlichen Verfahrens (Art. 278 Abs. 1 BStP).

Demnach erkennt das Bundesgericht:
1. Die eidgenössische Nichtigkeitsbeschwerde wird gutgeheissen, soweit darauf einzutreten ist. Der Entscheid des Bundesstrafgerichts, Strafkammer, vom 28. November 2005 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdegegner auferlegt.
3. Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Strafkammer, schriftlich mitgeteilt.
Lausanne, 21. Dezember 2006
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: