first, i would prefer to use a new indicator in the fringe, when the
    fringe is present - seems like this would be a nice use of that real
    estate, more suitable than precious minibuffer content space.  the new
    cue would display with the fringe top-of-buffer signal, when people
    use that, but that's generally redundant in the minibuffer, since it
    always has a prompt on the first line, and usually contains one or
    just a few lines.

I and, I think, many others, turn fringe off. Hate it; don't need it.

I think one or two characters of minibuffer space is not too much to
sacrifice for this feature, and it would be optional, in any case.

    second, you get many of the benefits you seek, and more, with
    something like icomplete.  with icomplete, on the third character you
    get a concise indication of the completion prospects, not just that
    completion is available.  a fringe indicator would not conflict,
    however, and would still be nice, though less necessary.

I do use icomplete, but some people do not. Even though I use icomplete, I
find the indicator helpful.

    > An additional subtlety can help a little more: I prepend a different
    > character (`=') and highlight it in a different color,
    > whenever completion requires a match.

    with icomplete you get different braces around the completion
    prospects depending on whether the match is required or optional.

You get different delimiters (parens vs brackets) only when there is only a
single match. When there are multiple prospects, you get braces for both
must-match and open completion.

Also, icomplete doesn't tell you anything until you start typing. So, until
you've narrowed down the completion to a single candidate, you don't know
whether completion is must-match or open.

    i think that having the option for an indicator in the fringe, whether
    or not you use something like icomplete, would be good.

Me too.

BTW - Attached are two small screenshots showing what this is like
(must-match: `=' and open: ` ') - when completion is not available, there is
no indicator. The screenshots also show icomplete at work (actually, my
version of icomplete:
http://www.emacswiki.org/cgi-bin/wiki/IcompleteMode#IcompleteModePlus).

If you're interested in trying my implementation of the feature, the code is
here (yes, it's a lot to load, just to see this feature, but you can always
toss it afterward ;-)):
http://www.emacswiki.org/cgi-bin/wiki/Icicles_-_Libraries.