Ahhhhhh....of course, now I get it.
DEP requires a setting named PAE to be enabled, which means Physical Address Extension
. Windows should automatically enable PAE during installation if your CPU supports hardware-based DEP and/or you have more than 4GB of RAM.
For some reason PAE must be disabled on your system. And the PAE setting is stored in the BCD...that's why Windows displays the message about bcdedit.
To enable PAE, open a command prompt with administrative privileges and type the following:
bcdedit /set pae ForceEnable
Then simply reboot your computer and try the DEP setting again.
(I still think you only need to enable DEP for Windows services etc., not for all programs on your computer. That way you don't have to add any exclusions to the list - but of course you can, if you prefer.)
Let me know if this works for you.