ArcMap legends, scale bars, and scale text don't resize when the page size is changed. This happens even if the Page Setup 'Scale map elements proportionally to changes in page size' option is selected.
Legends, scale bars, and scale text are sized according to the page size at the time they are inserted.
In versions 8.1.2 and 8.2, map elements and graphics resize in proportion. For data frames this is different now, for they used to resize to fit the page, even if it meant changing the data frame's aspect ratio.