EFI Boot Windows 8.1 or 10 Install on MacPro4,1 / Mac Pro (Early 2009)
Got it working finally...

The first trick is to remove ALL disks from the MacPro when trying to load setup. You may leave clean HDDs or SSDs where the Mac EFI cannot find MBR or Protected MBR.

After you removed all other disks the MacPro4,1 will not directly freeze after choosing EFI Boot on the installer stick.
(You will have to create it like mentioned before here to force an EFI boot of the installer.)
There will then be a progress bar loading files but unfortunately you will get stuck on a black screen in a few seconds... 

To be finally able to load setup you need to flash MacPro4,1 firmware to MacPro5,1 firmware.

The EFI version reported in rEFit shell will not change. But you will still have a different version after the upgrade flash. Apple does not seem to take great care about correct versioning with EFI standards as I understood from Rod Smith's comment here.
This more recent Apple internal version of the MacPro5,1's EFI will be providing us with the ability to boot EFI setup from the Windows 10 Installer on the MacPro4,1 machine.

Setup will load fine then and will give you a clean bootable EFI/GPT install of Windows 10 (W8 I did not try since I am happy with the more recent version). Install bootcamp drivers and enjoy AHCI without patches.

Be sure to strip the bootmgr files from the installer disc or stick. Even when choosing EFI boot, the Apple EFI will still boot the installer in BIOS/CSM Mode when those files are present.

I will probably post more detailed step by step instructions soon...

Here they are:


Make EFI bootable USB Installer


Download Win10 install ISO from Microsoft
Boot into Windows DVD Setup or existing BIOS/CMI installation to access a Windows command prompt
open command prompt (from windows run cmd, from setup press shift+F10)
load diskpart and make a clean installer stick
type in command prompt:

diskpart
list disk
select disk n #n=usb stick
clean #everything will get deleted!
convert gpt
create partition primary
format quick fs=fat32 label=Winstall
exit
exit 

mount downloaded install ISO (I did it in Windows, should work in OSX too)
drag everything from the mounted ISO onto the USB stick
delete bootmgr and bootmgr.efi files from the stick to avoid BIOS/CMI boot and force EFI boot. See also here

Flash MacPro4,1 with MacPro5,1 firmware

Bootrom MP41.0081.B07 (EFI 1.4) to Bootrom MP51.007F.B03 (EFI 1.5)
(If your machine shows Bootrom version MP41.0081.B08 you could first try to continue without upgrading. I don’t know which Apple EFI version is contained in there. Downgrading should be possible as well, definitely possible to version MP41.0081.B07. Please research if you don’t want to lose the downgrade possibility to MP41.0081.B08)
The upgraded EFI finally enabled me to complete the boot process and you will have all other advantages of the 2010 and later models (hex-core CPU, faster RAM, Audio over DP) This upgrade is reversible.  (If using El Capitan you need to disable System Integrity Protection. Otherwise the flash will not perform. If patch is running successfully you can see a big grey loader bar and the apple logo. Optical drives will open. See here how to easily disable SIP)


Dowload MacPro5,1 Firmware here
-Mount dmg
(above steps will avoid error 5570)
Download Mac Pro Firmware Upgrade Utility here
Run Utility and follow instructions
check upgraded bootrom version and identifier in System Information  

Setup Windows with EFI boot 


remove ALL disks from the Mac Pro
Plugin USB Installer stick
Boot Mac holding option/alt key
Choose EFI Boot
Enter setup and select GPT installation target disk
Install  

Install Bootcamp Drivers (optional of course.. You can also manually add what you want)


Boot into Windows
Download Boot Camp Support Software 5.1.5640 here
run setup
(the setup was hanging on my machine while installtion of the RealTek Audio drivers. To solve that follow instructions here)



Done.

Only issue I have is with my NVIDIA GTX 680 DVI-D port (and maybe others). After installing NVIDIA drivers screen will go black without signal. Booting then will show Windows logo but will go black w(o signal when login screen should appear. The system will boot to login properly after only 5-10 sec black screen without signal when using the DVI-I port instead. After successful login I could unplug and switch the port. Confirmed on EVGA and Gainward card. Did not have time to investigate further.