Sachverhalt: A. Am 18. Oktober 2000 reichte die Stiftung Sicherheitsfonds BVG beim Versicherungsgericht des Kantons Solothurn Klage ein mit dem Hauptbegehren, der Kanton Solothurn sei zu verpflichten, ihr einen Betrag von Fr. 5'851'866.90, zuzüglich Zins zu 5 % auf verschiedenen Teilbeträgen ab verschiedenen Fälligkeiten, zu bezahlen. Die Stiftung begründete ihre Forderung mit den von ihr infolge Zahlungsunfähigkeit der Vorsorgeeinrichtung der Firma H._ AG sichergestellten Leistungen, für die ihr gegenüber Personen, die für die Zahlungsunfähigkeit einer Vorsorgeeinrichtung ein Verschulden treffe, ein gesetzliches Rückgriffsrecht zustehe. Dieses werde gegenüber der Aufsichtsbehörde des Kantons Solothurn geltend gemacht. Gestützt auf einen entsprechenden Antrag des Kantons Solothurn beschränkte das Versicherungsgericht das Verfahren zunächst auf die materiellrechtliche Einwendung der fehlenden Passivlegitimation des Beklagten. Mit Entscheid vom 27. Juli 2001 stellte es fest, dass der Kanton Solothurn passivlegitimiert sei. B. Mit Verwaltungsgerichtsbeschwerde beantragt der Kanton Solothurn, der vorinstanzliche Entscheid sei aufzuheben und die Klage sei abzuweisen. Die Stiftung Sicherheitsfonds BVG und das Bundesamt für Sozialversicherung (BSV) schliessen auf Abweisung der Verwaltungsgerichtsbeschwerde. C. Das Eidgenössische Versicherungsgericht und die II. Öffentlichrechtliche Abteilung des Schweizerischen Bundesgerichts haben einen Meinungsaustausch geführt über die Frage des Rechtsweges bei Regressforderungen des Sicherheitsfonds gegen einen Kanton für sichergestellte Leistungen infolge Zahlungsunfähigkeit einer Vorsorgeeinrichtung. D. Am 4. Mai 2004 führte das Eidgenössische Versicherungsgericht eine publikumsöffentliche Beratung durch.