What are possible directories for .desktop files and their icons, and when to use what directory?

.desktop files

Globally installed applications have their .desktop file in /usr/share/applications. If a similarly named .desktop file exists in ~/.local/share/applications, it will "overrule" the global one (after log out/in after they were created). Local .desktop files are used for user-specific alterations of the functionality of the launcher, to add items to the quicklist (in Unity) e.g., or for locally installed applications.

The third directory you mention, /usr/share/app-install/desktop is used by Software Center, as explained here. Many applications don't use this one at all.

Icons

can technically be stored anywhere. Small applications can have their files (including icon) e.g. stored in one self-containing directory in /opt/<application_name>, but most of them will be found in /usr/share/icons/.
An excellent Question/Answer(s) combination on icons can be found here.