> or maybe find the first character that matches [:alnum:], and
> use that.

Sounds reasonable.

> Btw, can the other patch be installed _in_addition_ to the first one?
> IOW, they are orthogonal, or could be that, right?

Yes, they should be orthogonal. One patch turns regular input strings into regexps, the other patch uses character folding tables which have always worked fine with regexps.