Territorially organised states attempt to deal with the challenges associated with transborder mobility by structuring and controlling geographical and social mobility options. Once mobile persons are present on their territory, state authorities are dependent on ‘successful’ interactions with the people concerned in the attempt to implement migration and integration policies. This poses the question of whether and how the intrinsic logic of such interactions affects the institutions of mobility control. Our research project undertakes a systematic, in-depth investigation of interaction orders at local immigration authorities in Germany. Its key aim is to study the trajectories of interactions between persons with (long-term) exceptional leave to remain and immigration authority personnel. Central concerns are issues connected with mutual expectations and rules and the contradictions inherent in the negotiation and establishment of mobility options for people whose deportation has been suspended. We assume that the interaction order itself produces a range of paradoxes and generates precarious forms of residence that are not intended by either of the parties involved. The analysis of the tense relations between people with (long-term) exceptional leave to remain and the state authorities promises to generate new insights into processes of social and geographical (im)mobilisation.