I examine the robustness of monetary equilibria in a random-matching model, where a more efficient mechanism for trade is available. Agents choose between two trading sectors: the search and the intermediated sector. In the former, trade partners arrive randomly and there is a trading externality. In the latter, a costly matching technology provides deterministic double-coincidence matches. Multiple equilibria exist with the extent of costly matching endogenously determined. Money and “mediated” trade may coexist. This depends on the size of the probability of a trade, relative to the cost of deterministic matching. This outcome is inferior for an increasing-returns externality. Under certain conditions, regimes with only costly matching are welfare superior to monetary regimes with random matching.