Holy cow, I wrote a book!
The most important difference between My Documents and
Application Data is that My Documents is where users store their files,
whereas Application Data is where programs store their files.
In other words,
if you put something in CSIDL_MYDOCUMENTS
you should expect the user to be renaming it,
emailing it to their friends,
all the sorts of things users do with their files.
Therefore, files that go there should be things that users
will recognize as "their stuff".
Documents they've created, music they've downloaded,
that sort of thing.
On the other hand, if you put something in
the user is less likely to be messing with it.
This is where you put your program's supporting data that isn't
really something you want the user messing with,
but which should still be associated with the user.
High score tables,
spell check exceptions...
There is another directory called
(Local Settings\Application Data)
which acts like CSIDL_APPDATA,
except that it does not get copied if the user profile roams.
(The "Local Settings" branch is not copied as part of the
roaming user profile.)
Think of it as a per-user-per-machine storage location.
Caches and similar non-essential data should be kept here,
especially if they are large.
Other examples of non-roaming per-user data
%TEMP% and Temporary Internet Files
Temporary Internet Files