We treat several key stochastic equations for non-Markovian open quantum system dynamics and present a formalism for finding solutions to them via canonical perturbation theory, without making the Born-Markov or rotating wave approximations (RWA). This includes master equations of the (asymptotically) stationary, periodic, and time-nonlocal type. We provide proofs on the validity and meaningfulness of the late-time perturbative master equation and on the preservation of complete positivity despite a general lack of Lindblad form. More specifically, we show how the algebraic generators satisfy the theorem of Lindblad and Gorini, Kossakowski and Sudarshan, even though the dynamical generators do not. These proofs ensure the mathematical viability and physical soundness of solutions to non-Markovian processes. Within the same formalism we also expand upon known results for non-Markovian corrections to the quantum regression theorem. Several directions where these results can be usefully applied to are also described, including the analysis of near-resonant systems where the RWA is inapplicable and the calculation of the reduced equilibrium state of open systems. (C) 2011 Elsevier Inc. All rights reserved.