Hazard's stuff

GNOME applications, such as Evolution and Evince, use locale to figure out the paper size you want. So, to change paper type, you need to export LC_PAPER environment variable containing locale which uses the paper size you are looking for. E.g., for A4 paper:

export LC_PAPER="POSIX"

For Letter paper size:

export LC_PAPER="en_US"

My system locale is en_US and it seems that GNOME is hardcoded to use Letter paper size for this locale, which is wrong for the place I live in - the standard paper size here is A4.

It took me quite a few walks to the office printer to figure out this one...