Of course I have, but if somebody else stumbles upon that problem: I have found out what happens:
Windows 7 does not allow applications to store their configuration data in the program installation folder anymore, this is considered "bad" programming.
However, for old programs that do, it redirects these to the local user folder, i.e.
C:\Users\<UserName>\AppData\Local\VirtualStore\Program Files\Cave Story Deluxe\profile.dat