There are still problems: If I enter M-x ABÅjg, the result is not
    perfect -- but what's the alternative?

Would it be better to lose some height at the top, rather than only at
the bottom?  Currently, I think, g and q cannot be distinguished in
the default font.

In the long run, perhaps the best solution is to allow some extra
space under the minibuffer for the sake of such situations.  But that
can't be done until the Emacs frame height no longer has to be an
integral multiple of the line height.