Is that something public that I can try?
do you have mapImage aka map service layer or feature layer?
did you happen to try with A3 Landscape? you see the same problem?
you can of course try with your own print service with custom templates where you give more room for the legend element in the layout.