(N.B.: This is a blue-sky suggestion. Depending on the logfiles' sizes and maybe available resources it might be impractical, don't know. The approach has worked well for me for a certain class of text file messed-up-ness.)

Independent of newlines, is there a reliable way to tell where "real" lines, meaning actual log entries, end?

For instance, if whole log entries have fixed length you could remove all newlines, then break the combined text into fixed-length records. If it were that easy you'd probably have tried this, but maybe the approach can be altered to suit your situation -- if entries always end with some characteristic pattern that doesn't occur elsewhere in an entry, you could split just after each match of that pattern, and so forth. Maybe a combination of checking for a pattern within a certain range of possible lengths will do the trick.