I want to bump this post because I am having similar issues getting the legend to behave correctly.
We've put together a simple map maker application for others to quickly go online, select the layers they want to display, and print.
The template was setup with all of the layers from the map maker application in the TOC, turned on, so we could theoretically see the maximum size the legend could be. Once we had the columns, style, and size figured out, the layers were turned off and we had our template. However when you print, the legend does not respect the settings from the template. As items are added, the top of the legend moves up, rather than the bottom moving down. So we switched the position of the legend to the bottom of the page so as items are added, it will move up. This worked until we had too many items and no new columns were being created (even though we setup the legend to have 3 columns).
What are we missing here?