The reason malware likes to execute from these locations is because legitimate software likes to execute from these locations. They’re areas that the user’s account should expect to have some level of access to.
Based on a quick grep of my own system and a random end-user account on our network:
%appdata%
Right now, I’ve got Dropbox, the installer for Adobe AIR and a few Microsoft Office odds and ends in this folder.
%localappdata%
join.me and SkyDrive appear to live here, or at least to have driven through recently.
%temp%
Lots of programs, legitimate or otherwise, will want to execute from this folder. Installers typically unpack themselves to a subfolder of this when you run setup.exe on a compressed installer archive.
%UserProfile%
It will typically be safe unless the user has particular requirements, though note that at least some of the above folders could be subsets of this on a network with roaming profiles.
Compressed archives
Don’t run code directly, instead typically extract to %temp% and run from there.
As to whether or not you should block these areas, it depends what your users typically are doing. If all they need to do is edit Office documents, play Minesweeper during lunch, and maybe access a LOB app via a browser, etc. then you might not have too much trouble blocking executables in at least some of these folders.
Clearly the same approach won’t work for people with less well-defined workloads.