Ok, I've got spark and I've got fuel pressure, the efi relay is working and it does activate when hot.
I just came across an similar case but this was on an early 90's corvette, I don't know if I mentioned that I replaced a few injectors but I didin't check them before installing them. I bought those quite a while ago and they sat for a long time, the injectors are probably loosing impedance when hot or just sticking because I don't smell fuel after long periods of cranking when hot. I did this repair because one of my injector seals was leaking and the truck was running rough.
Same thing happened with the corvette, had spark, fuel pressure but it would crank and only start with a shot of fuel, injectors where replaced and problem was solved, they were stuck.
I will perform a few tests on the injectors but the safest thing to do is just remove them all and have them flow tested.
At least I am getting somewhere with this as it is quite frustrating by now, I will update you once I test the injectors. This is probably next month as I will be leaving the country for a few weeks.