Personally, I'm the only one who uses my computers, so I'm a big fan of the settings being stored in the program install directory. I try to keep my installed programs and my extracted programs separate. Installed programs go into D:\ProgNew and extracted programs go into D:\ProgNoInst. If I format my C drive all my programs in my D:\ProgNoInst folder still work after reinstalling windows. Also, if I want to move a program from one computer to another (or put it onto a flash drive) I can just copy them out of ProgNoInst, it's VERY convenient!
In situations where multiple users might use the same program it gets a lot more complicated. If user A changes the toolbar layout it should not be changed for user B. Storing the settings in the user folders could be helpful here, but requires switching users in Windows, which is an annoyance. A better solution IMO would be to have users choose a profile to use when the program starts. User A selects "John's Profile" and user B selects "Jane's Profile". If the content of the program is sensitive in some way (e-mail, passwords, whatever) then also have a password for each profile.
In fact, I could see a single user wanting multiple profiles. For example, maybe User A would want a "retouching" profile in Photoshop when he wants to
edit an existing photo and a "creation" profile when he's creating a new image. Maybe a "combo" profile as well that gives easy access to all the tools. Switching users would not be a viable option to have access to all these profiles.
Also, having everything in a single directory eases uninstallation; just delete the folder! No registry crap left behind, no "quick start" programs still starting with the computer using up RAM, nothing. Also, there's no worry about gaining rights to other user's folders.