> I can't reproduce either, which makes me suspect it has something to do
> with either multibyte character sets (Philipp, what's your $LANG ?) or
> a specific zstyle.

I have LANG=en_US.UTF-8
 
> [...]
> zstyle ':completion:*' format '%SCompleting %U%d%u%s'
>
> Philipp, do you use anything like that?

The .zshrc I use to reproduce this is

autoload -Uz compinit
compinit
zmodload -i zsh/complist
bindkey '^o' menu-select

I've just purged my Debian zsh so that there are no global config files 
left in /etc/zsh. Therefore I don't think any zstyle like this is active.