Finally, I've catched the bug. The major culprit is commit
a8be7c1ec40c9fab3407a0bc59e20141364e231f, which resulted in Tramp not
cooperating well with ido.el until tramp.el itself was loaded. It's an
autoload issue. There were other problems too, for example with commit
97776f295d652aff97be91431ad53db5618ad2a2 and its new function
`tramp-completion-handle-expand-file-name'. All of the changes are from
May 2016.
I hope I've fixed this now; I would be happy if somebody could
crosscheck. Likely, a bootstrapped version of Emacs is needed, due to
the changed loaddefs.el.