Eidsvig se hizo conocido a nivel nacional cuando el 14 de julio de 1976 fue arrestado por la KGB en Moscú mientras actuaba como mensajero para la organización en el exilio Alianza Nacional de Solidaristas Rusos. La misión de Eidsvig era entregar folletos, medicamentos y un manual de rebelión a un ruso en Moscú que había solicitado dicho envío. Mientras tanto, el destinatario había sido traicionado y arrestado. Los agentes del KGB esperaban en el apartamento la llegada de Eidsvig, que fue detenido. El hombre permaneció encarcelado en la prisión Lefortovo de Moscú durante 101 días antes de que las autoridades soviéticas decidieran liberarlo. Esto ocurrió después de que el ministro de Asuntos Exteriores, Knut Frydenlund, y el primer ministro, Trygve Bratteli, trabajaran para conseguir su liberación.[2]
El arresto atrajo considerable atención tanto en Noruega como en otros países, pero las reacciones fueron en gran medida negativas. La reconstrucción de los hechos que se presentó inicialmente estuvo influenciada por la desinformación soviética. Se alegó que Eidsvig había incurrido en una conducta que podría haber dado lugar a su arresto y que lo que había hecho era estúpido y ridículo. Entre otras cosas, se afirmó falsamente que estaba repartiendo folletos en la calle. Esta presentación de los acontecimientos permitió a la KGB utilizar recortes de la prensa noruega en sus interrogatorios para debilitar la resistencia de Eidsvig.[3]
Antes de su conversión al catolicismo el 20 de diciembre de 1977, estudió teología en la Universidad de Oslo con miras a ejercer el ministerio en la Iglesia de Noruega. También trabajó durante diez años como autónomo para el periódico Morgenbladet.
Después de completar sus estudios de licenciatura en el Heythrop College de la Universidad de Londres, fue ordenado sacerdote para la diócesis de Oslo en la Catedral de San Olav de Oslo por monseñor John Willem Nicolaysen Gran. Durante los siguientes cuatro años fue vicario parroquial de la parroquia de San Pablo en Bergen. Sirvió durante algún tiempo como capellán militar en las Fuerzas Armadas de Noruega, en parte en Evjemoen, al norte de Kristiansand, y en parte en la compañía de reclutamiento médico en Bømoen y Voss. El 1 de enero de 1986 fue llamado a suceder a Wilhelm Hertmann como párroco de San Pablo en Bergen. En ese tiempo, Eidsvig trasladó, amplió y reconstruyó la escuela católica parroquial; mientras trabajaba como profesor en la escuela parroquial. También participó activamente en la asociación lingüística Riksmålsforbundet.[4]
Fue miembro del consejo presbiteral (1983-1990), del colegio de consultores (1987-1990) y del consejo pastoral (1988-1991).[4]
En el verano de 1991, Eidsvig abandonó Noruega y fue acogido como novicio en el monasterio de Klosterneuburg de los Canónigos Regulares de San Agustín, en las afueras de Viena. El 27 de agosto de 1991 recibió el hábito monástico y el nombre de Markus. El 30 de agosto de 1995 emitió la profesión solemne. Posteriormente fue vicario parroquial de Klosterneuburg-Stiftspfarre (1992-1997), maestro de novicios de la abadía desde 1996 hasta su nombramiento episcopal y párroco de la iglesia de San Leopoldo en Klosterneuburg (1997-2003). Bajo su liderazgo, el monasterio asumió un sabor más internacional que antes: además de algunos austriacos, recibió candidatos de otros países como: Estados Unidos de América, Alemania, Noruega y Vietnam. También fue consejero y secretario del capítulo de la orden.[4]
