By the way, here's a patch of how the regexp version can apply to both
isearch and query-replace while doing pretty much everything that's
been requested.
It fixes the issues raised by Eli, and (unlike the previous version)
is now fully implemented.
Now, "a" will match any character whose decomposition has "a" as the
first letter character (not necessarily the first character), so it
will match ⒜, for instance. "a" also matches the decomposition itself,
so it will match both the letter "á" and the two-character combo "á".
Note that the unicode characters still only match themselves, because
that's also how case-folding works (if you search uppercase you only
match uppercase).

I believe that is all we were asking for, correct?

Shall I merge? (It adds about 5 seconds of compile time in my laptop)