Deploying virtual machines - Windows Guest/Linux Host or vice versa?

You'd need to go Windows host and linux guest for photoshop performance. I'm not sure what issues with the registry you'd be concerned about since the guest OSes would be in a different environment. Vmware would be the virtualization layer of choice. You might also look at seeing if they even need to use the linux portion. There may be ways to eliminate the vmware portion altogether.

Agreed with everyone else, and also slightly puzzled about your "cluttered and slow" registry comment. Whatever are you or your users doing that could cause this? "Cluttered and slow" registries died out with Windows 98, if they ever even existed in the first place.

In my experience, if you need to utilize advanced hardware fully (especially graphics cards) you should do so with the host OS. While some virtual machines have the ability to "pass through" pieces of hardware for use with the guest OS only, I've only seen it done with USB ports - not sure it's workable with the graphics card.

VMware workstation on a Windows host. This is going to give you the best Guest OS graphics performance. The other "server" virtualization solutions aren't going to do much for running Photoshop in the guest other than give you the ability to do it with the virtualized graphics drivers.

VirtualBox on Windows. It also sounds as though you want to sort out a disk re-imaging system of some kind so that when the users have stuffed their copy of Windows full with spyware and browser toolbars - or cluttered up the registry, or whatever it is they do these days - you can simply wipe and reinstall the Windows partition of your machine. You might want to split the hard drives up into several partitions, so users can keep My Documents on one partition and you can re-image a machine without them losing any files.