Sachverhalt: A. Der Inhaber der Firma Y._ ersuchte das Bundesamt für Sozialversicherung (BSV) am 22. November 2001 um Erteilung der Betriebsbewilligung unter der Leitung von Dr. med. X._. Dr. med. X._ erwarb nach dem Medizinstudium in München vom Bayerischen Staatsministerium des Innern die Approbation als Arzt (Approbationsurkunde vom 4. Mai 1983). Vom 15. Januar 1984 bis 31. Dezember 1987 war er am Institut für Toxikologie und Umwelthygiene der Technischen Universität in München tätig. Von der Fakultät für Medizin der Technischen Universität München erwarb er den akademischen Grad eines Doktors der Medizin (Promotionsurkunde vom 30. März 1989). Vom 1. Januar 1988 bis 31. Mai 1990 war er Assistenzarzt am Krankenhaus für Naturheilwesen in München, wo er eine Weiterbildung im Bereich Innere Medizin absolvierte. Daraufhin war er vom 1. Juni 1990 bis 30. Juni 1993 am Institut für Klinische Chemie und Laboratoriumsmedizin des Klinikums der Stadt Nürnberg tätig, wobei er gemäss Bestätigung von Chefarzt Dr. med. W._ vom 1. Juni 1990 bis 31. März 1992 im Rahmen seiner Weiterbildung zum Laborarzt den Teilbereich Medizinische Chemie absolvierte. Von der Bayerischen Landesärztekammer erhielt er das Recht, die Bezeichnung "Laborarzt" zu führen (Anerkennungsurkunde vom 6. Mai 1992). Laut Beschluss des Zulassungsausschusses Ärzte Mittelfranken vom 23. Juni 1993 wurde ihm daraufhin die Genehmigung zur Ausübung einer vertragsärztlichen Tätigkeit als Laborarzt erteilt. Vom 1. Juli 1993 bis 31. Dezember 2001 war er Laborleiter und Teilhaber einer Gemeinschaftspraxis für Labormedizin in Nürnberg. Mit Schreiben vom 10. Februar 2002 teilte Dr. med. X._ dem BSV mit, er beantrage die Anerkennung der Gleichwertigkeit seiner Aus- und Weiterbildung für den Facharzttitel FAMH (Schweizerischer Verband der Leiter medizinisch-analytischer Laboratorien) in den Bereichen klinische Chemie, Mikrobiologie, Infektions-Immunologie und Hämatologie. Gleichzeitig legte er Zeugnisse und Bescheinigungen auf über seine bisherige Aus- und Weiterbildung. Das BSV holte daraufhin eine Stellungnahme des FAMH-Fachausschusses ein zur Frage der Gleichwertigkeit der Weiterbildung mit der FAMH-Weiterbildung zum Spezialisten für labormedizinische Analytik. Dieser verneinte die Gleichwertigkeit mit einer monodisziplinären FAMH-Weiterbildung in den Fachgebieten Hämatologie, klinische Chemie, klinische Immunologie oder medizinische Mikrobiologie sowie mit einer pluridisziplinären FAMH-Weiterbildung in den vier Fachbereichen. Zudem umfasse das pluridisziplinäre FAMH-Weiterbildungsprogramm seit dem 1. März 2001 auch die medizinische Genetik. Hinweise auf eine diesbezügliche Weiterbildung fehlten jedoch. Gestützt darauf eröffnete das BSV dem Gesuchsteller am 5. März 2003, dass seine Qualifikationen den Weiterbildungsgrundsätzen der FAMH nicht entsprechen würden und es deshalb beabsichtige, das Gesuch um Anerkennung der Gleichwertigkeit seiner Laborweiterbildung abzuweisen. Gleichzeitig gab es Dr. med. X._ Gelegenheit zur Stellungnahme. Dieser hielt mit Eingabe vom 8. April 2003 an seinem Gesuch fest. Mit Schreiben vom 18. August 2003 bestätigte das BSV seinen ablehnenden Standpunkt, worauf Dr. med. X._ um Erlass einer anfechtbaren Verfügung ersuchte. B. Mit Verfügung vom 5. November 2003 lehnte das Eidgenössische Departement des Innern (nachfolgend: Departement) das Gesuch des Dr. med. X._ um Anerkennung der Gleichwertigkeit seiner deutschen Laborweiterbildung mit dem schweizerischen FAMH-Weiterbildungstitel in Hämatologie, klinischer Chemie, klinischer Immunologie und medizinischer Mikrobiologie ab. C. Dagegen lässt Dr. med. X._ beim Schweizerischen Bundesgericht Verwaltungsgerichtsbeschwerde führen mit dem Antrag, in Aufhebung des vorinstanzlichen Entscheids sei der deutsche Laborweiterbildungstitel anzuerkennen; eventuell sei die Sache zur ergänzenden Abklärung und Neubeurteilung an die Vorinstanz zurückzuweisen. Nach durchgeführtem Meinungsaustausch überwies das Schweizerische Bundesgericht die Angelegenheit am 23. Dezember 2003 an das Eidgenössische Versicherungsgericht. Das Departement schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde.