While I have encountered similar problems, the only solution I have found is the Microsoft's universal solution:  "use FDISK on your computer and reload the operating system".

Yes, this is not a helpful answer however after repeated attempts to fix things the only practical solution was wipe the system and reload the OS.  Every time I have gotten a DEP error it boiled down to a improperly installed application.

Vista and your ANTI-VIRUS solution of choice will insist that it must have DEP.