The All Users folder is actually a symbolic link to the c:\ProgramData directory. ProgramData contains junctions (also hidden) to directories in the Public profile (c:\users\public by default).
If you look at the hidden directories, you'll notice you won't have permission, even as admin. This is so you don't mess up the links. As for why it's like this, it's for backwards compatibility reasons, for apps that are hard coded to use things like documents and settings, for example.
So the short answer to your question is to use the Public\Desktop directory.