We describe a new algebra of boundary value problems which contains Lopatinskii elliptic as well as Toeplitz type conditions. These latter are necessary, if an analogue of the Atiyah-Bott obstruction does not vanish. Every elliptic operator is proved to admit up to a stabilisation elliptic conditions of such a kind. Corresponding boundary value problems are then Fredholm in adequate scales of spaces. The crucial novelty consists of the new type of weighted Sobolev spaces which serve as domains of pseudodifferential operators and which fit well to the nature of operators.