Microscale robotics represents a promising future for minimally invasive medicine. However, one of the biggest challenges of microrobots moving through the human body is represented by the complex 3D structure of biological lumina and tissues, which obstructs the navigation of micron-sized devices. Here, we fabricate ultra-deformable magnetic microrobots, consisting of ferrofluid-loaded lipid vesicles, and we magnetically pull them through chambers that exert upon them a gradually more forceful confinement. We thus analyze their capability to face interstices comparable to or smaller than their characteristic size and their consequent behavior in terms of stability, velocity, and deformation. The results show that the inherent compliance of these vesicle-based magnetic microrobots allows them to infiltrate successfully in interstices slightly smaller than their size. Further enhancement of their compliance and the development of specific control strategies may lead to microrobots able to move through interstices and traverse complex biological environments.This article has been submitted to IEEE Transactions on Medical Robotics and Bionics (manuscript TMRB-07-24-BR-0017) and presented at the IEEE RAS EMBS 10th International Conference on Biomedical Robotics and Biomechatronics (BioRob 2024), 1-4 September 2024 Heidelberg, Germany.