Hi Miguel,
If you want to use ESRI's print solution (PrintDijit or PrintTask), using Templates to determine the page size, layout and orientation might be the only way to go, and I believe might be the easiest way per design perspective. Otherwise, you may end up developing custom solution on your own.
Good luck.
Understand. But I believe creating 40 map templates takes much less effort than developing custom print solution. Map templates are very easy to create, maintain, and deploy. They are scalable as well. Even if you develop custom solution, you will still need to figure out how to deal with different page sizes, orientation and custom layout options. I used to develop one template, but to use CSS and JS to control the layout, orientation and paper sizes. But trust me, it is not fun. I'd go for ESRI's solution if that works for you.
If you still like to consider developing custom print solution, you can develop server object extension either using ArcObjects or arcpy.mapping. Here is the link that may be useful: http://resources.arcgis.com/en/help/main/10.1/index.html#//01540000056t000000. Stay away from Web ADF. It's deprecated.