This is a riff of Sylvester's answer, which I upvoted for the "compose > export to pdf > print (at size)" workflow. This is exactly what we do with costs-the-earth-Arcgis, and have been for years. Some of our maps are quite complex and/or large (up to 42"x 72" or 105cm x 180cm). More than a few just refuse to print directly. Sometimes it's Arcmap that craps out and sometimes the printer, or something in between. Whatever the reasons, we've found creating PDF and then printing from that to be the most stable and flexible route.
Compose the map at the largest page size that works, then use your favourite pdf-reader's ability to "scale to page" or "fit to page". Depending on the output device, it may be possible to use the print driver's Advanced or Page Layout properties to up-scale the map by a percentage. This is preferred over fit to page as it gives you more control over the scaling. For example an 18"x24" (45cm x 60cm) pdf with a map scale of 1:500,000 up-scaled 200% will yield a hardcopy of 1:250,000, whereas with fit to page you might get something weird like 1:254,350 (and never be quite sure what it actually is).
The "export to pdf" stage can be substituted with "print to pdf" with a virtual pdf printer (pdfcreator highly recommended; just say "no" to installing the dumb browser toolbar).
So, to sum: choose the best map composing package you can afford and are willing to work with, then use other tools for sizing.