ASRock X99X Killer Fatal1ty3.1 takes several boots

Are you using the latest BIOS version?

It is possible that the PCIE power could be responsible for your problems yes. I find it concerning that your PSU does not have a native one, if this is the case then it is likely that your PSU does not properly support Haswell CPU's power requirements. The adapter method would likely be fine on a less high end system but for a 2011 enthusiast grade system you may be falling a little short of the mark in sustained power output, especially at boot when components are initialized and causing spiked power consumption. 

Thanks for the clarification, you meant the molex connector on the board not an adapter 

It is an optional feature that provides additional power to the PCIE slots so yes you could connect it with a second GPU installed but it is not required. I would only use it if I had say 2 titan Zs or Fury Xs in my system as the PCIE slots should be more than able to handle the power requirements of most current GPUs, especially the Nvidia's Maxwell line which are fairly low power for their performance. The power hungry R9 290x may have benefited from the molex connector on the board in crossfire configurations for example. Even then I would only connect it if my GPU was unstable due to power starvation. 

I am afraid not, while I am a Moderator here I do not work for ASRock. If you want info on the ETA of an update you can contact tech support here. You can also inform them about your problem and see if they can create a BIOS to help you if the steps I suggested don't help. Just make sure to link to this thread in your ticket so they can see what you have already tried. ASRock tech support have been very accommodating with this in the past and tend to be very helpful with UEFI issues when contacted directly. ASRock_TSD is the tech representative here on the forums but they are not on all that often as the forums are only a small part of their responsibilities.