ProgramData is the "right" place in most circumstances, but you have to deal with the security on subfolders and files created there.
I just made a small program with two buttons. One button creates a file under ProgramData and writes a line of text there with the curent date and time. The other button opens the file back up, reads the line of text, and displays it.
I ran the program once elevated ("run as administrator") and clicked the 1st button to create the file. Then I waited a few minutes and reran the program without elevation and clicked the 1st button again, replacing the file with a new file having the new timestamp in it.
After this I ran the program a 3rd time, elevated again, but clicked the 2nd button to retrieve and show the timestamp written in the file.
Then I ran the program a 4th time, unelevated, and clicked the 2nd button to read/display the timestamp line of text again.
The 3rd and 4th runs display different values because they are reading two different files!
The unelevated runs were actually working against a file named:
[tt]C:\Users\<user>\AppData\Local\VirtualStore\ProgramData\pddemo\file.txt[/tt]
The elevated runs work against the file:
[tt]C:\ProgramData\pddemo\file.txt[/tt]
To prevent this from happening you need to create the "pddemo" folder and set security on it to give all necessary users full access, or at least read, write, modify, and probably list contents. By default folders created here get a special set of ACLs granting "owner access." This means whoever creates a file has full access to it, but other users get read-only access. As I said before, generally your installer package would be responsible for taking care of this.
A non-owner trying to replace or modify such a file results in a virtualized file being created, unless the process is marked "Vista aware" which results in a security exception.