We finally found a work-around.
We had to change the settings on the default network printer which was installed on the computer from letter to A4. Afterwards, once we restarted the computer and tried printing from SAP, it was printed out to A4. Letter was still shown as paper size, but the printouts were in A4. Very special… but it is working properly now.