On all the turbojets that I have flown the maximum altitude a pilot can attempt a restart is 30,000 FT MSL. What factors go in to deciding what the maximum altitude is for an engine restart / relight?
Basically, it gives the pilot the altitude and airspeed at which the engines can be relighted in flight. Based on these values, the pilot has to take a decision to descend etc. A jet engine requires (compressed) air, fuel and a flame source for (re)starting. So air density plays an important part in determining the maximum restart altitude.
In addition, there are other factors at play as well. In case of unassisted (without APU, for example) windmill restarting, the airspeed must be enough to overcome the inertia of the components. In certification memorandum on Turbine Engine relighting in flight, EASA says,
.. as core - bypass ratio of engines continues to increase, higher airspeeds are generally required to enable unassisted windmill restarting. The inertial effects because of the increased size, mass, and number of engine driven gearbox accessories may also contribute to increased rotor drag loads, decrease starting performance, and possibly contribute to rotor-lock conditions.
In case a starter is available, the airspeeds required go down (as APU itself is usually a small turbine, the altitude effects are not as pronounced). According to CFR § 25.903 Engines:
(2) An altitude and airspeed envelope must be established for in-flight engine restarting, and each engine must have a restart capability within that envelope.
(3) For turbine engine powered airplanes, if the minimum windmilling speed of the engines, following the inflight shutdown of all engines, is insufficient to provide the necessary electrical power for engine ignition, a power source independent of the engine-driven electrical power generating system must be provided to permit inflight engine ignition for restarting.
The engine restarting envelope is decided both in terms of altitude and airspeed. It also depends on aircraft. For example, in ETOPS aircraft, the APU must be designed to have airstart capability throughout the normal flight envelope. Regarding this envelope, EASA says,
2 Envelope of Altitude and Airspeed
2.1 Sufficient flight tests should be made over the range of conditions detailed in 2.2 and 2.3, to establish the envelope of altitude and airspeed for reliable engine restarts... The effect of engine deterioration in service should be taken into account.
2.2 Altitude and Configuration. From sea-level to the maximum declared restarting altitude in all appropriate configurations likely to affect restarting, including the emergency descent configuration.
2.3 Airspeed. From the minimum to the maximum declared airspeed at all altitudes up to the maximum declared engine restarting altitude. The airspeed range of the declared relight envelope should cover at least 30 kt.
Like most chemical processes, combustion becomes easier and faster with higher pressure. The combination of speed (which provides ram pressure) and altitude (which provides atmospheric pressure) must result in sufficient pressure in the combustion chamber. That is the reason for the stepped altitude limit. If density were the reason, there would not be a need to reduce the maximum restart altitude at lower speed.
For combustion to take place, first the fuel droplets injected into the air stream need to evaporate. This is made easier by higher temperature and pressure, and the lower both are, the more residence time of the fuel-air mixture in the combustor is required for good combustion. Next, the ignition system will add enough activation energy to start the combustion process. When the fuel-air mixture arrives at the ignitor, the fuel must have sufficiently mixed and evaporated for ignition to occur.
In case of the turbojets you have flown the pressure above 30.000 ft will not be sufficient to light the fuel, especially at the low compression ratio of the starter-driven or windmilling compressor.