Hi everyone,
I'm coming to this conversation a bit late. I found this thread because I was having the same issue as the OP, Doug. Good thing I read all the posts because the answer is here after all! It dawned on me when I read the post from Jeremy8000 on page one of this thread, then reading a few of the posts after it.
First of all, I highly suspect that the speech recognition software that runs on Android and, by extension, Google Now is not, in fact, written by Google but rather licensed by them. If that is indeed the case, it would go a long way towards explaining why no one has been able to get a concise answer. Additionally, Google is such a huge and completely opaque organization, I am floored that Doug was able to actually come up with a toll-free support number. That in itself is amazing.
So back to the original problem. My results are from testing on my Galaxy Note II running Android 4.3 and dictating into a Samsung provided app called "S Note" and also "TweetCaster", for my money the best Twitter app out there. Identical results were obtained on my 2013 Nexus 7 running Android 4.4.2 (there used to be a fantastic car called the "442", but that's another thread!) and again dictating into "TweetCaster".
The key words are "return" and "new paragraph" spoken once and at a leisurely pace. In fact, I tried skipping a beat and then speaking "return" and it still worked. You can also skip a beat with "new paragraph". The phrase "new paragraph" works in all circumstances. The word "return" woks ONLY after PUNCTUATION - and PUNCTUATION is the key here. Read Jeremy8000's post on page one and you'll see all his sentences end with punctuation and only then does he speak a formatting command.
You can say "return" as fast as you like and as often as you like, but if it is not preceded by punctuation OF SOME SORT, e.g. "comma", "question mark", "period", "exclamation point", it simply will not work. The speech recognition engine cannot understand why you'd want to go to a new line when you have not terminated the preceding one. As we all know, punctuation terminates sentences.
By contrast, the same engine doesn't seem to care when or where you want to start a new paragraph or under what circumstances. The end result is that you can say "new paragraph" anywhere you want, with or without preceding punctuation, and Android will dutifully skip TWO lines and give you your paragraph.
Hope this helps clear things up!