Here is another useful bit of information. Using Haiku Installer, when it formats a BeFS partition, it doesnt modify the GPT UUID partition code. It still maintained the previous OS partition code, and the EFI loader would struggle to identify a Haiku partition. I had to manually scan for bootable devices every boot, and play with safe mode settings to get 2 in 3 chances of booting. Once I discovered this issue, I used gdisk (a GPT version of fdisk) to modify the GPT UUID partition code to Haiku (42465331-3BA3-10F1-802A-4861696B7521, from https://en.wikipedia.org/wiki/GUID_Partition_Table). Once I fixed the GPT UUID parition code, Haiku would boot perfectly 100% of the time straight from Refind. The EFI loader would successfully find Haiku and boot it without any safe mode settings.
So when booting from EFI, check that the GPT UUID partition code is correct. You can use the DriveSetup utility to verify that the partition code displays Be File System. I fixed it using Linux tool gdisk (instead of fdisk). Good luck.
PS - potentially our Drive Setup tool would need to be updated so that it writes the GPT UUID partition code of Haiku (42465331-3BA3-10F1-802A-4861696B7521) when formatting a Haiku disk.