Hi Ergus and Joćo,

As I explained in a separate thread, at the moment the best way to 
implement icomplete-vertical (and in general to display completion 
candidates in the minibuffer) is to convince Emacs to start displaying the 
minibuffer at its beginning.  This avoids all known problems.

With this solution, displaying completion candidates after point in a 
minibuffer is a trivial task: it suffices to insert the completion 
candidates in the minibuffer, and Emacs will display as many of these 
candidates as possible, given the user preferences 
(max-mini-window-height, resize-mini-windows, ...), the size of the Emacs 
frame, the phase of the moon, ...  This works on Emacs 24, 25, 26, 27 and 
28, with fixed and variable width fonts.

Part 1 of the solution (which solves the "root" problem, and is not 
specific to icomplete-vertical):

(defvar-local start-display-at-beginning-of-minibuffer nil)
(defun start-display-at-beginning-of-minibuffer (&rest args)
   (when (and start-display-at-beginning-of-minibuffer (minibufferp))
     (set-window-start-at-begin (point-min) (point))))
(defun set-window-start-at-begin (beg end)
   (when (< (+ beg 2) end)
     (set-window-start nil beg)
     (unless (pos-visible-in-window-p end nil t)
       (set-window-start-at-begin (+ beg (/ (- end beg) 2)) end))))
(add-hook 'window-scroll-functions #'start-display-at-beginning-of-minibuffer)
(add-hook 'post-command-hook #'start-display-at-beginning-of-minibuffer)

Part 2 of the solution (which implements icomplete-vertical):

(setq icomplete-separator "\n")
(add-hook 'icomplete-minibuffer-setup-hook (lambda () (setq start-display-at-beginning-of-minibuffer t)))
(defun icomplete-vertical-reformat-completions (completions)
   (save-match-data
     (if (string-match "^\\((.*)\\|\\[.+\\]\\)?{\\(\\(?:.\\|\n\\)+\\)}" completions)
         (format "%s \n%s" (or (match-string 1 completions) "") (match-string 2 completions))
       completions)))
(advice-add 'icomplete-completions :filter-return #'icomplete-vertical-reformat-completions)

The only limit of this solution is that is is not possible to display an 
ellipsis ("...") at the end of the completion candidates list, to indicate 
that some completion candidates are not displayed.  This is a minor 
limitation, and IMO using one screen line just to display "..." is a waste 
of resources.

Gregory