This is actually not an issue of
multicol but a general problem with a core functionality of LaTeX. You get exactly the same kind of behavior if you replace
\index or ...
The issue is that these "invisible" commands internally use
\@esphack to hide themselves and to avoid that you end up with two spaces (on the left and the right). Problem is they keep the space on the left and suppress (if it exists) one at the right.
But because of the invisible command (in case of
\columnbreak that is a
\vadjust) the space is not removed by the
\par command. Thus you end up with a framebox of exactly the width of a line + 1 space (that results in the second line).
If however you first end the paragraph it will be 1 line long.
The general answer is attach "invisible commands to a previous word if they are used in horizontal mode, especially at a paragraph end. (a % for example would do too)
Maybe something can be done about this but I think this would be rather dangerous to change the behavior of
\@bsphack and friends.