Is "re-" really a useful prefix? What newbie will type "re-" when
they need regexp-related functions? Where would they get the idea
that "re" stands for "regular expression”?

Just as an example, since I started programming with Python, I’m quite familiar with “re”. “Regexp” is also fine, I don’t have a strong opinion on this (especially for there are quite a few regexp-prefixed functions in Elisp).