🚀 go-pugleaf

>It's almost as if re-search-backward works by moving backward a
>character at a time and calling re-search-forward with the appropriate
>arguments, although I'm sure that's not quite the way it's done.

I looked at this issue of "reverse-regexp-search" quite a bit.
My conclusion was that in addition to the limited functionality
provided by the current re-search-backward (which really does
move back point by point and then look forward), what you need
is a reverse-regexp-search.
  Our Common-Lisp Emacs provides such a feature.  The big difference is that
you must write your regular expression as seen from the BACK!  One over that
hurdle, you just teach the regexp processor to index the character buffer in
reverse, and Voila!  you can search backward for the longest section
matching the regexp...
 [actually, instead of teaching the regexp engine to go backwards,
  a temporary buffer is created which contains the buffer segment 
  to be searched, and that temporary buffer is reversed.]

You can probably create this functionality from the privitives already
available to elisp (might want to use C code to create the tmp buffer
with chars reversed)  Maybe someday the C regexp engine will be extended
to actually go backwards.

Maybe somebody could get really creative and acually parse a regexp
and reverse it automatically (this is easier when the regexp is in
functional notation, rather than in string format...)