Immigration detention and deportation are central tenets of the British government's immigration strategy. Although in theory immigration detainees face imminent deportation, in practice many obstacles frustrate removal, prolonging the limbo of detention. Drawing on two years' anthropological research with failed asylum seekers in one such Immigration Removal Centre, I argue that the concepts of identity and identification are useful in understanding these situations of impasse. Many detainees struggle to meet official expectations and requirements regarding the nature of identities and how they can be proved. They frequently have no identity documents (or those they have are considered false), come from countries with minimal registration systems, or are generally assumed to be lying. Many also have their identities ‘disproved’ by UK Border Agency caseworkers as part of having their asylum claims refused. The combination results in some individuals lacking a bureaucratically recognised identity or alternatively being saddled with multiple identities. This hinders their removal as a ‘genuine’ identity must be re-established in order for the embassies to issue travel documents. I examine what happens when people fall between having one identity disputed and another officially confirmed, arguing that when stuck in this way people become vulnerable to criminalisation and exceptional treatment such as indefinite incarceration. My premise is that as identity databases and verification techniques infiltrate British society, from high-level security debates to daily banality, those people beyond identification techniques become increasingly bureaucratically problematic, making them simultaneously threatening to and vulnerable to state apparatus.