This post offers a solution (amongst others), which I should have tried before posting this.
tldr: Set the "Legend: Plot Minimum" property to the number of plots in the graph.
The property name and its documentation seem to suggest a solution to the opposite problem: The number of entries in the plot legend will never go below this value.
That's what threw me off, because I was looking for something that would make sure the number of entries in the plot legend will never go above this value. As it turns out, this property node also has the effect of removing "unused" plot names when the number is set to the amount of plots in the graph.
And in 2014 it also works with scroll bars in the legend without having to turn them off and on again.
Delete Plot Names From Legend.vi