Sachverhalt: Sachverhalt: A. A._ (geboren 1955) reiste am 10. August 1991 erstmals in die Schweiz ein und arbeitete an verschiedenen Orten, teils mit, teils ohne Aufenthalts- und Arbeitsbewilligung. Seit April 1995 war er für die Temporärfirma I._ bei der Einsatzfirma R._ tätig, ohne über eine Aufenthalts- oder Arbeitsbewilligung zu verfügen. Am 26. Dezember 1998 erlitt er eine schwere Hirnblutung, die einen fast einjährigen Spitalaufenthalt erforderlich machte. A._ erhielt am 9. Juni 1999 rückwirkend per 16. Februar 1999 eine Aufenthaltsbewilligung Kurzaufenthalter "L"; am 8. Dezember 1999 verliess er die Schweiz. Mit Schreiben vom 23. April 1999 ersuchte A._ bei der CSS Versicherung (heute: CSS Kranken-Versicherung AG; nachfolgend: CSS) um Aufnahme in die obligatorische Krankenpflegeversicherung. Die CSS lehnte sein Gesuch mit Verfügung vom 3. Dezember 1999, bestätigt mit Einspracheentscheid vom 21. März 2000, ab. Die hiegegen erhobene Beschwerde wies das Versicherungsgericht Basel-Stadt (heute: Sozialversicherungsgericht Basel-Stadt) mit Entscheid vom 20. Dezember 2000 ab. A._ liess Verwaltungsgerichtsbeschwerde führen, welche das Eidgenössische Versicherungsgericht mit Urteil vom 24. Dezember 2002 (K 38/01) in dem Sinne guthiess, als es den kantonalen Entscheid aufhob und die Sache an die Vorinstanz zurückwies, damit diese nach erfolgter Abklärung neu entscheide. Die CSS stellte am 27. März 2003 ein Erläuterungsgesuch, auf welches das Eidgenössische Versicherungsgericht mit Urteil vom 28. April 2003 (K 42/03) nicht eintrat. Die CSS stellte am 27. März 2003 ein Erläuterungsgesuch, auf welches das Eidgenössische Versicherungsgericht mit Urteil vom 28. April 2003 (K 42/03) nicht eintrat. B. Mit Entscheid vom 10. Dezember 2003 hiess das Sozialversicherungsgericht Basel-Stadt die Beschwerde des A._ gut, hob den Einspracheentscheid vom 21. März 2000 auf und wies die Sache zum Erlass eines neuen Einspracheentscheids im Sinne der Erwägungen an die CSS zurück. B. Mit Entscheid vom 10. Dezember 2003 hiess das Sozialversicherungsgericht Basel-Stadt die Beschwerde des A._ gut, hob den Einspracheentscheid vom 21. März 2000 auf und wies die Sache zum Erlass eines neuen Einspracheentscheids im Sinne der Erwägungen an die CSS zurück. C. Die CSS führt Verwaltungsgerichtsbeschwerde mit dem Antrag, der vorinstanzliche Entscheid sei aufzuheben; eventualiter sei die Sache zur genaueren Abklärung des zivilrechtlichen Wohnsitzes an das kantonale Gericht zurückzuweisen. A._ schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde. Das Bundesamt für Gesundheit, Abteilung Kranken- und Unfallversicherung, verzichtet auf eine Vernehmlassung.