My understanding is that the maximum altitude at which an engine can be started may be below the maximum operating altitude, provided it's documented in the AFM.
That sounds reasonable, and I've flown turbine twins like that.
However, I would not approve a single engined aircraft to operate at an altitude higher than I could prove engine restart ability - what reason would there be to do that? I see no reason to cool the engine of a single engined aircraft, during a glide down to the maximum starting altitude, to then really have to work at getting it running again. Just tell the pilot not to fly that high, it's simpler.
As I mentioned, the manufacturer does not always state in the flight manual
why a limitation is placed on an aircraft.