Abstract: The bulk-boundary correspondence (BBC), i.e. the direct relation between bulk topological invariants defined for infinite periodic systems and the occurrence of protected zero-energy surface states in finite samples, is a ubiquitous and widely observed phenomenon in topological matter. In non-Hermitian generalizations of topological systems, however, this fundamental correspondence has recently been found to be qualitatively altered, largely owing to the sensitivity of non-Hermitian eigenspectra to changing the boundary conditions. In this work, we report on two contributions towards comprehensively explaining this remarkable behavior unique to non-Hermitian systems with theory. First, we analytically solve paradigmatic non-Hermitian topological models for their zero-energy modes in the presence of generalized boundary conditions interpolating between open and periodic boundary conditions, thus explicitly following the breakdown of the conventional BBC. Second, addressing the aforementioned spectral fragility of non-Hermitian matrices, we investigate as to what extent the modified non-Hermitian BBC represents a robust and generically observable phenomenon. Graphical abstract: [Figure not available: see fulltext.].