Disobey the max alt. Once you reach 18,000ft set your altimeter back to 29.92 and you should be able to make your assigned alt. flawlessly.

There is a knob on the altimeter (the analog one) that you can turn by clicking on the left and right of it or by turning the scroll wheel on your mouse while hovering your pointer over it to set it.

FL390 between London and Paris sounds like an overkill, that flight can't be more than 200nm...and you need atleast 100 miles for your descent.

And yes, the 737-400 is not certified above FL370, but if you wanna try again at FL390, try to reduce the fuel load if you haven't done it before.. From London to Milan you can have the wingtanks full, and add 1000lbs to the centretank, this will give plenty of fuel, more than enough for the flight and if you need to divert

And I don't see how reseting the altimeter would do any good (in Europe we do it way earlier than 18.000ft) since I don't think Satz has changed it in the first place - hence he already has it at standard 29.92in hg/1013 hPA 

Just my take

Yeah, 39,000ft is quite overkill for that short flight (which I've made in a C182S) I would cruise at around 20,000ft for a flight that short (6,000ft in the 182S).