Windows 8 bothers me again

So it happens... I boot my computer on Windows 8 to try a software that I couldn't manage to run under Debian Jessie, to check whether it is worth all the pain. While testing this software in Windows 8, this OS was updating, though I was completely unaware of this (It is my fault to not deactivate automatics update from the very first day?). When I decided I want to go back to Debian and restarted the machine, I got this friendly screen saying that I should not turn off my computer becuause W8 was configuring the updates. "Ok!", I thought, "I did not know it, but that's ok.". 
The process took hours and when it was finally finished and the pc restarted , it booted directly into W8 without passing through GRUB, "UhOh..." 
I immediately went to the internet and found that that GRUB is easy to re-install. I grabbed a copy of live Debian, and made a bootable USB. I could boot from the USB and followed the instructions from the dpkg bot at irc channel #debian-next:

To reinstall boot to your Debian install disk/live CD, switch to the other console (Alt-F2), then mount your root filesystem (mount -t "fs type" /dev/"partition" /target ; mount --bind /dev /target/dev ; mount -t proc none /target/proc ; mount -t sysfs none /target/sys), then chroot into it (chroot /target) and run update-grub && grub-install /dev/"device".  Also works for EFI.

I did this and rebooted. Sadly it did not work and I got:

Reboot and Select Proper Boot Device

Since then (it has been 3 days! I wish I could sue MS for all the time wasted!) I am trying all suggestions I get that do not look too dangerous. I am about to re-install my Debian, but I am not sure this will solve the problem.

Technical data

Machine: ASUS K55V

It is a UEFI machine but I have

Fast boot [disable]

Secure boot [disable]

Launch in CSM [enable]

      PXE OpRom [disable]

As far as I understand this means that I am in BIOS compatible mode.

My Disk was partitioned in the following way (it has a protective MBR strcuture)

EFI partition

Windows partition

Some KiB not allocated

Root partition

Swap

Home partition

This worked fine until the update in question. Following a suggestion from user amphi in #debian-next I added a 1 MiB BIOS Boot partition (shrank the EFI partition by 1 MiB). I thought this did not make sense, cause the system worked for 1 year and half without this partition, but when everything fails, you do what is left. The disk now looks like

EFI partition

BIOS Boot parition

Windows partition

Some KiB not allocated

Root partition

Swap

Home partition

The only effect of this is that my BIOS/EFI now detects 2 windows bootable sectors instead of just one.

Ideas?

Will re-installing Debian solve the problem?

What should I do with the EFI partition? Back it up (it has the bootloaders) and then remove it completely?