Why can't I drive more than one H-Bridge unless all other output pins are in Hi-Z state?
As always, it's the last thing you look for. Just before posting the question, I thought to also have a look at the input pins of the unconnected motor.
Lo and behold, something strange:

At 10ms and 0.5V per division, this seems to be some signal with a period of ~20ms, at ~0.8V peak-to-peak. 20ms equals 50Hz. See where this is going yet?
This pattern emerged because I had connected the probe ground to the Arduino ground, which is powered by my PC's USB port, and the probe's micrograbber to the H-Bridge input, which was powered by the lab supply. And that's where the problem was; Lab supply and Arduino were not grounded to one another directly, so the signal levels between them picked up noise from the grid.
Once I connected the DC grounds of lab supply and Arduino together, everything worked perfectly fine and I can now even drive two motors at the same time.
Hope someone will find this helpful in the future!