Note: this is issue does not seem to happen on all category pages; At https://en.wikipedia.org/wiki/Category:Futurama for instance, it displays as it should.

That's because the monotype part of the message ("[[Category:Rivers of British Columbia]]") is contained in a <span class="nowrap">, so the text is not line-wrapped just as requested. As it's wider than the area for edit notices, it overflows it, and the rest of the message fills out the space.

This should probably be fixed in the appropriate template, but I guess VE could enlarge the editnotice area if needed (not sure if it's a good idea).

Agreeing with MatmaRex here; this is something that should be fixed in the template.