Here are a few more observations.

(1) Recall a consequence of Dirac's Theorem: A simple graph $G$ on $2n$ vertices admits a one-factor if $\delta(G) \ge n$. (This is a sufficient, but not necessary, condition.)

So, should Zach Wolske's set $D$ induce a subgraph which is at least "half dense", then $D$ contains a perfect matching and his argument works for simple graphs too. A similar thing holds for the set of even vertices $N$ by considering the complement of the induced subgraph. In general, it's polynomial to check for the existence of a perfect matching.

Pushing this a little further, I suspect that obvious graphs are the majority of almost-regular ones (but I have not worked out the details).

(2) As you know, there are various regular graphs which admit no perfect matching. (By the above comments, these graphs need to be fairly sparse.) As examples, there are odd cycles and also that famous cubic graph on 16 vertices (see http://mathworld.wolfram.com/PetersensTheorem.html).

If $G$ is any of these "bad" (say $r$-regular) graphs with $r$ odd, then the disjoint union of $G$ with $K_{r}$ provides a non-obvious almost regular graph. You can't add a matching to the clique, and you can't take one out of $G$. This sort of generalizes the complete bipartite $K_{n,n+1}$ counterexample (upon considering the complement).

(3) I am almost certain you know about Yuster's work on one-factors in almost regular graphs, but those who don't may find this helpful: http://research.haifa.ac.il/~raphy/papers/match-regular.pdf