Oh, that's why ^J is a literal newline in Emacs. How did I miss that for 25 years?
(BTW, for anyone curious, you match a newline in a regexp in emacs by using ^Q ^J, the first is the quote operator and the second is the character you want, ^J, or newline)