Hi Ergus,

I don't understand why you change so many things in icomplete.el for 
icomplete-vertical.  I attach a patch which implements icomplete-vertical 
by adding only 20 lines to that file.  It seems to work correctly.  Use it 
with:

(icomplete-mode 1)
(setq icomplete-vertical t)

and set `icomplete-prospects-height' to the maximal number of completion 
candidates you want to display, for example:

(setq icomplete-prospects-height 10)

Gregory