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 (My Documents), you should expect the user to be renaming it, moving it, deleting 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 CSIDL_APPDATA, (Application Data), 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, program settings, customizations, spell check exceptions...

There is another directory called CSIDL_LOCAL_APPDATA (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 are your %TEMP% and Temporary Internet Files directories.