>
> It doesn't seem to work, though. From emacs -Q:
>

Tramp doesn't behave as expected with only flex in completion-styles, 
indeed.  I see the same problem in Emacs 27.  Your bug report was similar 
to bug#50387, it is in fact related but subtly different.

>
> The hostname isn't completed and I don't see the *Completions* buffer. 
> While without enabling fido-vertical-mode, I get /ssh:server on pressing 
> TAB after /ssh:s
>

I'd suggest to add something a fallback method in 
icomplete--fido-mode-setup, for example completion-styles '(flex basic). 
And perhaps to apply the attached patch in your local Emacs, which 
provides I think the behavior you expect.