Can you briefly let us know if the starter cranks the engine? Also do you hear the fuel pump humming when you put the key in on ON?
So, from what I understand, sounds like you may have a broken ground/wire on one of the solenoids. I had a similar incident on a 4runner, also on the highway - the 4Runner engine stops running (no warning sign, just turns off) suddenly when cruising at regular speeds, then it came back on briefly...then again turned off. The starter cranks the engine fine.
Try gently pulling on the wire harnesses that are going to/away from the solenoids. It may allow the engine to run when you start it, but it wont actually fix the issue and most likely will happen again.
If you are ok working with wires, you can manually add a ground wire to the the solenoids' ground connection to see if it will work.
But do trace the problem with a volt meter for continuity.
Let us know.