Hence even perfect versions of grep will slower by arbitrarily large factors, depending on the input.
So while there may be problems, expecting no difference or no significant difference between encodings is not correct either
That you get UTF-8 input and produce UTF-8 output doesn't imply you are better off using UTF-8 for processing. Translating UTF-8 to fixed-width UTF-32 and back is of linear complexity and takes small, fixed amount of memory. The only trade-off is when processing /very/ long lines -- up to four time more memory would be used for buffer.
As mentioned in other posts, Unicode requires normalization of certain character combinations into other characters, so you'll be processing all input characters anyway. Just prefix an extra step to it, not even a separate loop.
And so you can do Boyer-Moore with Unicode at very little extra cost :-)
Some text-intensive programs of Plan 9, including grep, use internally fixed-widht format called `Rune' for unicode, exactly for reasons of performance. UTF-8 input is translated into strings of Runes for processing and translated back for output.