Motile cells often explore natural environments characterized by a high degree of structural complexity. Moreover cell motility is also intrinsically noisy due to spontaneous random reorientations and speed fluctuations. This interplay of internal and external noise sources gives rise to a complex dynamical behavior that can be strongly sensitive to details and hard to model quantitatively. In striking contrast to this general picture we show that the mean residence time of swimming bacteria inside artificial complex microstructures is quantitatively predicted by a generic invariance property of random walks. We find that while external shape and internal disorder have dramatic effects on the distributions of path lengths and residence times, the corresponding mean values are constrained by the sole free surface to perimeter ratio. As a counterintuitive consequence, bacteria escape faster from structures with higher density of obstacles due to the lower accessible surface.