I have exactly the same problem with having only 50 legends at maximum in a plot. It is a decision for users to plot a limited number of legends and not to Matlab. Of course, many legends will make graphics rather confusing, but I have circumstances that I need more than 50 legends. The two column option doesn't solve that, because it is still limited to 50.
Another option (set(gcf,'NextPlot','add'), newP = copyobj(c,newAx);etc.), which Walter showed somewhere else, works to show all legends, but the highlighting of Markers-Lines is limlited to the 'active' first 50 legends.
So Matlab, please solve this limitation problem of 50 legends (like it was in the past) and let users decide how many legends they want to project.