For your first question the answer is yes, but probably you need to look at specific examples worked out using Kazhdan-Lusztig theory. It should be enough to look at type $A_3$ (as BGG did), where values $>1$ start to appear for some K-L polynomials evaluated at 1. I believe the hand computations by BGG were quicker for an irregular weight, but that's not essential. [As you've recognized, their notation for highest weights incorporates the $\rho$-shift in a sometimes confusing way. Similarly, I've tended to use "regular" in the BGG category as shorthand for "dot-regular" relative to the shifted action of the Weyl group. But that doesn't affect your questions.]
Concerning your second question, it seems (from K-L theory) that a simple description of $N(\lambda)$ occurs mainly when $\lambda$ is dominant integral (regular doesn't matter then). See for instance section 2.6 in my book on the BGG category (AMS, 2008), for the case of a dominant integral weight. This relies mainly on the early work of Harish-Chandra but was re-emphasized by Verma in his 1966 thesis and came to play a major role in the development of the BGG resolution.
[ADDED] If you want concrete examples showing that $N(\lambda)$ need not be the sum of Verma modules, you have to introduce more notation and do some careful bookkeeping with weights and Weyl group elements. This is probably not rewarding, as a quick review of the history shows. I'll refer to some sections of my book, which provide a unified exposition based on older papers.
By about 1970, BGG had refined Verma's ideas enough to see that $N(\lambda)$ is a sum of naturally embedded Verma submodules (neessarily having multiplicity 1) if $M(\lambda)$ has no repeated composition factors. (See my section 5.1, especially the remark and exercise.) This follows indirectly from their study of strongly linked subweights. A converse statement is less direct: If $M(\lambda)$ has a repeated composition factor $L(\nu)$, then for some strongly linked subweight $\mu$ of $\lambda$, $M(\mu)$ has a repeated composition factor $L(\nu)$ and $N(\mu)$ fails to be a sum of Verma submodules.
After another decade, the proof of the 1979 Kazhdan-Lusztig conjecture on composition factor multiplicities made it clear that (in principle) these multiplicities could be computed recursively in terms of values of certain (inverse) Kazhdan-Lusztig polynomials at 1. The full computation relies also on Jantzen's translation functors. Study of K-L polynomials then shows that multiplicities $>1$ only begin to occur in rank 3, as the $A_3$ example of BGG suggested. This depends on the Weyl group, which for the Lie algebra of type $A_3$ is the symmetric group $S_4$. Here there are two pairs of permutations which lead to multiplicities $>1$. For all integral weights in suitable Weyl chambers (and some singular weights on walls), one then gets examples of Verma modules which you ask about. Labelling relevant weights by Weyl group elements requires some care here. (See my sections 8.3-8.4.)
P.S. I should have mentioned a pre-KL paper by Deodhar and Lepowsky, which uses various methods to deal with the regularity question in most types; this is mostly superseded by the stronger information given by Kazhdan-Lusztig theory combined with the interpretation of coefficients of their polynomials in terms of the Jantzen filtration. Elsevier seems to have opened up their archives for online access, so the paper is freely available
here.
