Not minutes, hours, nearly 2 hours to be precise (09:30 to 11:24). And the intercept only happened because the 737 was in a holding pattern.
The B-777 had just left KUL airspace, when the incident occured. It took a while to liaise with Vietnam's controllers who couldn't find the traffic on their scopes or communicate with it. They usually assume the aircraft is on the wrong frequency. They call on the emergency guard frequency and then ask other traffic in the area and neighboring control centers to try to establish some contact with the airplane.
All this takes time, before a search procedure is initiated. The lack of a transponder contact in all zones, initially meant that the aircraft probably crashed in the Gulf of Thailand.
Nobody thought at the time, that the aircraft turned around stealthily, heading towards the Indian Ocean. As the threat level is very low in Malaysia, it is not inconceivable that military radar coverage would be minimal, especially after midnight. I'm not even sure that the alarm was raised with the military in time to identify a target and scramble interceptors, as the plane was thought to be somewhere else.
Satellites are good at picking up distress signals, but not at finding stealth aircraft in the middle of nowhere, in real time.