First...you're wasting money on premium fuel...it doesn't want it or need it. 87 octane is fine for it. Anything over is just money down the tubes.
Now that I have that outta my system...there's a multitude of things that can do this....first you'll have to determine if you have both fuel and spark (back to basics)...otherwise we are totally guessing.
I have to admit I'm ignorant of the immobilizer light...this a stock passive security system, like my VATS key on my Chevy? Most of those systems the light does come on when you start it, but most people never notice when it starts normally, they're not looking for an answer like you are....I'm guessing that's normal, but can't say with confidence...
That initial run of the pump , if it come on then stops, waiting for the motor to start, should let it run about the amount of time you are describing, then die if the pump fails to restart...it sounds pretty likely that's gonna be involved here.
The pump is cooled by the fuel in the tank...that might be why adding fuel seems to help.
Anyway, maybe try depressing the schreader valve on the fuel rail when it's not starting...see if there's any fuel present (careful, under high pressure) if not, you are on the right track. It can have pressure present and not start, it takes a minimum pressure before the injectors will open (typically 35-45 psi), but if you find very weak or no pressure, the answer is pretty clear.
Then just to find out why...would have to investigate the fuel pump, it's relay, and the timer/pressure feedback circuit to make sure there's nothing wrong there...