Transformer overheating reasons
What mechanism could possibly cause the losses in a transformer to
  increase at a higher supply voltage? I was expecting it to be larger
  at a lower supply voltage, due to the higher primary's current.


The main mechanism is transformer core saturation - as the supply voltage rises the losses in the core can rapidly become the dominant factor in terms of power loss.

What you should do is prove that at higher voltages on the AC supply (but with a light load 
of say 100 mA), the temperature rise is nearly the same - this would tell you that it is likely to be core loss, specifically hysteresis loss AND, if this is too much then a bigger core would be needed.


  I am aware that a transformer can suffer from overheating e.g. if it
  is over-driven / saturated, however, it does not seem to be the case
  here.


If it does not get excessively warm when the supply voltage is at the design maximum then it isn't a core loss problem but an \$I^2R\$ problem. You do need to be absolutely sure that the MOSFET isn't producing the heat though. Ditto the snubber circuit (not shown on the circuit in the question).