A little soapbox first: Personally, I don't see any advantage to "branding". If my company didn't write the software I don't consider it a "badge of honor" to stick my name on that software seeing as how, when there are problems with it I won't actually be able to solve them. You're addressing this to sysadmins but, perhaps, you're thinking more about a "Managed Service Provider" audience (who seem to just eat up this kind of stuff. I'm thinking about the various outsorced backup companies, for example, who let their "partners" slap a logo over top of the actual provider's name...)
If I substitute the words "customized configuration" in place of "branding" I find that your query is very pertinent to the type of work I do preparing third-party software for deployment to PCs and servers in my Customer sites. (I'd love it, personally, if the third parties would just start using Windows Installer and quit it w/ the custom SETUP.EXE deployments... GRR!)
All that aside, to address your specific questions:
Would you want to brand the installation process itself, or just the final product?
If only the final product, is it acceptable to run a seperate distribution step to apply the branding or should it be included in the install?
I'd perfer to see branding added after a "stock" installation of the "final product". That gives me an option to always install a "stock" distribution and to revise the "branding" resources separately from the software itself. Something applied after-the-fact would be good.
With MSI-based setups, for example, I see applying a transform file (MST) as being a modification to the "stock" deployment, but I always have the option to "fall back" to the stock deployment if I want to be sure that my "branding" isn't causing a problem.
How would you manage changes between versions of the product?
Ideally you'd maintain backwards-compatibility with prior branding resources such that the same "branding" process would work for future versions (failing gracefully when the older versions of branding resources don't have values specified for future branding mechanisms). I'd maintain the branding resources in version control like I do with configuration files, MSI transforms, etc.
What formats are easier to work with?
Executible binaries pose potential problems in a Windows "AppLocker" environment where they might need to be signed. I'd prefer that the branding be kept in a non-executible file. A JAR file (a ZIP file, basically) would be fine, as would "bunch o' files".
Considering different deployment scenarios, would there be any difference between
Server product, maybe multiple servers and User desktop product - These would be installed via Group Policy Software Installation Policy or startup scripts, so there's no difference. Ideally, the branding step could be as simple as installing an addt'l MSI that puts a "magic file" (or magic "bunch o' files") in the right place and the branding "just happens".
Server product that also acts as distribution point for desktop product (like JNLP, msi, plugin) - I don't use products like that, because I don't allow users to install software. If I were going to do something like that I suppose I'd have the product installer access a defined DNS name in the local DNS zone via HTTP (HTTPS, etc) to download the branding from a defined file name (think "http://productname-branding.yourdomain.com/branding.zip"). Then distributing the branding would be a matter of putting the branding file(s) up on a web server.
What other pain do software providers put you through in a corporate environment when deploying software with your brand on it?
I've never had the opportunity to "brand" any software, so I can't say.
In thinking about "customized configuration" as opposed to "branding", having comprehensive documentation about the configurable features, as Chris S says, is a good thing. Very rarely have I run into products that do a good enough job describing their various configuration mechanisms and how to manipulate them (other than through the UI). Personally, I think that any UI configuration interface should have a "supported" method of programmatic manipulation w/o requiring any user interaction, as well. I don't necessarily need to know about your various opaque binary configuration data repositories, but I want good interfaces to let me maniuplate the configuration from a script / installer, etc.
I think you're really targeting this question more at the type of Sysadmin who fancies themself a "Managed Service Provider" (MSP). In such a situation everything I'm saying above is probably wrong. An MSP would probably want branding to be integrated directly into an installer such that they could hand out the EXE, MSI, etc, to their Customers and the branding would occur "magically" during the installation.
From a the perspective of being a Customer for an MSP who was using software like this all I'd ask is to give me an automated way to install and uninstall your product in a determinstic and reliable way and I'd be happy.