This paper addresses two puzzles in the semantics of connected exceptive phrases (EP): (i) the compatibility of EPs modifying noun phrases headed by the negative polarity item (NPI) determiner any and (ii) the ability of a negative universal quantifier modified by an EP to license strong NPIs. Previous analyses of EPs are shown to fail to solve these puzzles. A new unified solution to the two puzzles is proposed. The crucial insight of the analysis is to allow von Fintel’s (Natural Language Semantics 1: 123–148, 1993; Restrictions on quantifier domains, PhD dissertation, 1994) leastness condition on EPs to be imposed at scopes non-local to the surface position of the EP. A general result is derived concerning the truth conditions of sentences in which an existential modified by an EP occurs in the scope of a downward entailing operator. The distribution of EPs is argued to depend on how the leastness condition interacts with other pragmatic strengthening conditions, such as the one imposed on any by Kadmon and Landman (Linguistics and Philosophy 16: 353–422, 1993).