>> As for making hi-lock-mode detect whether or not a regexp is multi-line,
>> isn't that a computationally non-trivial problem?
>>     
>
> Well, you can turn the regexp into a DFA, then take the ".*\n.+" regexp,
> turn it into another DFA, take the intersection of the two DFAs, and if
> it's empty you know your regexp can never match a multiline element.
>   

If you are going to go that that trouble, perhaps there is a better 
solution:

The Rx pattern matcher found in distributions of GNU Arch has these
relevant capabilities (relevant at least so far as I understand the 
problem you
are trying to solve):

1. It does on-the-fly regexp->DFA conversion, degrading gracefully into
    mixed NFA/DFA mode or pure NFA mode if the DFA would be too
    large.   The calling program gets to say what "too large" is.

2. Although it is a C library, you can capture what is (in essence) the
    continuation of an on-going match.   That is, you can suspend a
    match (or scan) part-way through, then later resume from that point,
    perhaps multiple times.   (This does not involve abusing the C stack.)

3. It does have some Unicode support in there and, though these capabilities
    are under-tested and some features are missing, it is quite flexible 
about
    encoding forms.

4. The DFA construction is "caching" and, for a given regexp, all uses
    will share the DFA construction.   E.g., multiple, suspended regexp
    continuations can be space efficient because they will share state.

5. Because of the caching and structure sharing, you can tell if two 
continuations
    from a single regexp have arrived at the same state with a C EQ test 
("==").

How can this help?

Well, instead of using heuristics to decide where to re-scan from and 
too, you
can cache a record of where the DFA scan arrived at for periodic 
positions in the
buffer.   Then begin scanning from just before any modification for as 
far as it
takes to arrive at a DFA state that is the same as last time, updating 
any highlighting
in the region between those two points.

I don't mean to imply that this is a trivial thing to implement in Emacs but
if you start getting up to building DFAs (very expensive in the worst 
case) and
taking intersections (very expensive in the worst case) -- both also not 
all that
simple to implement (nor obviously possible for Emacs' extended regexp 
language) --
then the effort may be comparable and (re-)visiting the option to adapt 
Rx to Emacs
should be worth considering.

As a point of amusement and credit where due, I think it was Jim Blandy 
who first noticed this
possibility in the early 1990s when I was explaining to him the 
capabilities I
was then just beginning to add to Rx.

This is a very old problem, long recognized, with some work already done on
a (purportedly) Right Thing solution.

-t