How many symbols are missing from your legend? We recently had the same problem and it seems to be due to ArcGIS dropping items when they don't fit.
Even if part of an item does not fit, the entire legend item is going to be dropped from the legend. For example, if only 10 classes from a 15 class legend item will fit, the entire item will be dropped, not just the 5 classes that do not fit. At this point the legend will stop trying to add items even if another legend item later in the list would fit. |
From Working with legends—Help | ArcGIS for Desktop (about 2/3 of the way down the page).
We tried creating a two-page mxd template, but that is not supported, so our solution was to create a new template mxd (called 'Legend Only') where the legend took up the whole page and the dataframe was so small you couldn't see it. Now users can do two exports - one with the map and one with the legend.