The problem is that ICU's sort_key (ICU == International Components for Unicode, sort_key == the unicode sort key generator) orders the list differently from ASCII order, putting '!' and '+' after '-' instead of before it. Calibre tells the Qt completer that the list is ordered, so unless the search gets lucky (the binary search hits exactly), the out-of-order items are never found. The same problem exists with accented characters like é, because ascii and ICU disagree about the order.
Two possible solutions:
1) change to an ascii ordering. Not sure this will really work in the face of non-ansi (larger than 255) unicode characters.
2) Tell the completer that the list is not ordered (c.setModelSorting(QCompleter.UnsortedModel). This works because the completer scans for a match, but will be somewhat more costly if the completion list is very long. My guess is that unless the list is in excess of hundreds of thousands, the performance penalty won't be visible.
I leave it to the owners of completer.py to decide what to do.