Jeppesen ATC section lists procedures for uncoordinated flight over the red sea, but the non-RVSM altitudes are FL250/260.
Why don't you just get Saudi overflight clearance? at least that way you would have ATC coordination in case of any inflight emergency.
The fax number for Western ATC is 966-12-685-4016 and tel 0532
Good Luck