I think we should remove that, and leave behind an alias that uses
utf-8-hfs, which is provided by Emacs. There's no reason to maintain
2 identical definitions.

Sounds reasonable. The implementation is vastly different, so getting rid of one is definitively an improvement.

When you set file-name-coding-system to nil, Emacs uses
default-file-name-system, which is utf-8, so it doesn't
compose/decompose characters, and that's why you see what you see.
IOW, using nil is a step backward.

I couldn't agree more!

What does this return:

M-: (file-name-all-completion "åäö" "/that/empty/directory/") RET

It returns nil.

Also, what is your value of completion-ignore-case?

It's nil.

Just out of curiosity -- how does `file-name-all-completions' work? Is the FILE argument encoded to decomposed form, is the file list converted to composed form, or is this handled by the comparison functions?

-- Anders