Just wanted to update this thread in case this can help anyone else in the future with similar issues. After resigning to the fact the the ECU might be shot, I had one last idea, which was to call AEM tech support in the states. I sent him an email explaining my problem and he replied saying it sounded like something was interfering with the signal. Some kind of accessory, maybe something with a relay. He said the EMS V2 either works and its shot, there never normally intermittent. Any way he said get the car started or at least try, the after turning it off, disconnected the negative battery for 30 seconds then try. I did this a few times and each ime it started on the first or second try. So seemingly something was causing this. Firstly I thought immobilizer so starting working out how to disconnect that, but after tidying up the under dash wiring I thought the only other new thing with a relay is the push start or the LED rear lights. So pulled the lights relay and tried again. Well wouldn't know it, start first time every time.
So it turns out the relay was either not grounding properly, or had a funny connection. This was causing the ECU to think it was still on even when the car had been stopped, so when you came to start it again it was confused until I had turned the key enough times that it clicked back into life again. Mad how it can be something lie that.
Anyway will monitor it for now just in case, but also wanted to thank everyone for all the comments/posts/suggestions especially Chris Wilson for his expert testing methods