A key feature of many real-world matching markets is congestion, i.e., market participants struggle to find match partners. We characterize congestion in a model of random matching markets where an agent pair must perform an inspection to verify compatibility prior to matching with each other. Motivated by the notion of regret-free stability, we assume agents are only willing to inspect their current favorite agent and will do so only if, upon a successful inspection, that match is guaranteed. We ask when, in large random two-sided markets, will information deadlocks arise in which many agents delay inspections indefinitely awaiting a match guarantee. The market consists of N women and αN men. We obtain a sharp characterization of the existence and size of information deadlock as a function of the men-to-women ratio α, women’s average size K of the consideration set, and an inspection’s success probability p, as N grows. Our analysis is inspired by the machinery of message passing and density evolution from statistical physics. We find a phase transition from a deadlock-free regime (where a vanishingly small fraction of agents are stuck waiting) to the information deadlock regime as we increase K, decrease α or decrease p. A number of market design insights emerge from our characterization, for example, the market connectivity K which maximizes the number of matches formed is that which causes the market to be at the phase boundary between the deadlock-free regime and the deadlock regime. Vertical differentiation between agents reduces deadlock, as does a willingness by agents to perform parallel inspections.