Medieval European maps were oriented every which way (well, within the cardinal directions). The fixation on a north=up orientation occurs with the revival of the Greek/Ptolemaic mapmaking tradition during the Renaissance. It might have even been a direct influence from Ptolemy's map (Geography was translated into Latin in 1407) and the numerous duplications of it, but it's hard to say for sure.

The interesting thing is that medieval Arab geographers had had access to the Geography and the Ptolemaic map tradition for centuries already, and were using it nicely while Europeans preferred a "sacral geography" map that was more openly ideological (all maps are political, of course). But the Arab preferred a south-up orientation.