Currently, the output paper sizes for PS and PDF templates are hard coded in the formats. However, the hard coded value is 'letter' which isn't usable in Europe (and possibly other parts of the world).
Better would be to allow a setting in System->Defaults at minimum and using that value in the templates.
One can imagine paper size selection based on the country of a customer, if the output is going to be sent by e-mail, to make things more complex. However, I think the System->Defaults is a good place to start and call this request finished.