Little sad to see that in many such questions are answered by "Limited" or "No" Linux support. I gathered that....
I my case Microsoft is not a option - sorry....
Any way I managed to solve the issue - here is what was done.
The CMOS, Factory reset and battery removal - all did not remove the UEFI boot entries. I can sort of see why, however, why is there no option within the BIOS to remove unwanted entries?
Anyway, once I had built the Debian 7.1 system, and ensuring it was booting use UEFI, it was just a matter if running, (as root)
and run the efibootmgr command to remove the offending entries.
This can also be done using live Ubuntu disk and as far as I can rememberer the Debian live disk worked as well - as long they are booted using UEFI. I did this be ensuring that UEFI boot option was selected in the BIOS, and the boot device is selected from the UEFI options.