I had some more time to test this (now on kernel 4.1.4 and X server 1.17.2) and
have made two hopefully useful observations:

* The Catalyst driver (version 15.7) is always able to initialize the setup
even though VGA-connected monitor seems to always "flicker" two times before
reaching the final mode.

* I have found a somewhat reliable workaround to use with the free driver: By
adding

xrandr --output VGA-0 --off

before

xrandr \
    --output VGA-0 --preferred --primary \
    --output DVI-0 --preferred --rotate left --right-of VGA-0

to my .xinitrc, the system will properly initialize both displays even though
the first command seems to take around two seconds to complete.