The Short time and Long time formats seem to be kept in HKCU\Control Panel\International as sShortTime and sTimeFormat, respectively. I did a quick test with manually tweaking those values, logging off, and logging on again, and the clock in the system notification used the time format I had configured.
The built-in Regional settings Windows Common Setting captures everything under that key, so you could create a personalization config file based on that setting, log on with a test user, configure the time format (and possibly some other regional settings) to your users' liking, log off, and import the resulting profile archive as a (default) predefined setting, either directly, or after a small edit to remove irrelevant settings.
I add the attached registry settings (in DEM section "User Environment" - "Registry Settings") to configure all region specific settings (date, time, language, currency, ...).
This works perfectly for me.
Flex Profiles.reg 16.2 K