Now, who here would say that the NSA isn't backdoored into every cell tower on that planet. I wouldn't be surprised if they are. How could we not know as soon as one of the cells on that plane popped up on a tower anywhere in the world? So, exclude all cell tower coverage areas in projected flight area and search there to rule out potential hijack/landing.
But assuming that a phone does make contact, there would be massive cooperation required to detect it. The airline and victims' families would have to give a list of phone numbers that could be on the flight, and all the carriers in the region would search through their towers' logs to see if any of those IMEIs (assuming they keep those logs for at least a week).