Does Microsoft have a best practices document regarding the storage of App Data vs User Data on different Windows Platforms?

There's a good description here of the various CSIDL values and the folders they refer to (including a description which should hopefully tell you what you need to know).

It also contains links to the functions you should use to retrieve these special folder paths.

Note that, as of Vista, the method has changed a little. It now uses KNOWNFOLDERID instead of CSIDL and the functions have changed as well. See here.

You can still use the older functions (at the moment) since I believe they're now just wrappers around the new ones. At some point in the future, that may change.

These are usually described in the Windows Software Logo Program (link broken). The link is to the Windows 7 logo requirements document, but similar documents exists for XP, Windows 2003, Vista and Windows 2008. In the Technical Requirements section you'll find some of the information you're looking for:

All application data that must be shared among users on the computer should be stored within ProgramData

All application data exclusive to a specific user and not to be shared with other users of the computer must be stored in Users\<username>\AppData

In “per-machine” installations, user data must be written at first run and not during the installation. This is because there is no correct user location to store data at time of installation.

EDIT:

Windows 10 users, look for the Certification requirements for Windows Desktop Apps (Section 10)