Software installation policy is processed before Startup Scripts are executed. Sometimes that's exactly what you want, and other times it's not. You can't change it.
When I want a startup script to run before software installation I end up using group membership to control the execution of the startup script and I end the startup script with a command to add the computer to a second group that controls software installation. The only problem with this is that, to date, I have yet to find any reliable way to restart a Windows XP or newer OS from a startup script. (Yes, yes-- I've tried a variety of methods, too. I can discuss them in detail if you'd like.) As such, this always makes this strategy require two boots to "take effect".
You mention "preferences", so I think you're looking at doing things to the user's environment via a logon script. Logon scripts are executed, obviously, after logon. If you're looking to check to see if a piece of software has been installed during the logon script query the Windows Installer "database" in the registry to see if the program is there and "bail out". You'll find the installed products in the "HKEY_CLASSES_ROOT\Installer\Products" key. Obviously, you'll have to figure out the GUID for the package you're dealing with.
Edit: Group Policy client-side extension (CSE) processing order is performed based on the value of the GUID for the client-side extension, from what I've been able to glean from documentation. It looks like the CSE's with numerically higher GUIDs execute later. I don't have the GUID for the "Preferences" CSE handy so I can't tell you how it should act re: running before / after other CSE's.
On Windows XP, at least, dig into HKLM\Software\Microsoft\Windows NT\CurrentVersion\WinLogon\GPExtensions and look for the CSE for "Prefernces". REGEDIT will sort those GUIDs numerically, too, so you could be able to tell, visually, if that "Preferences" CSE is going to execute before/after other CSE's.
Local Group Policies get stored outside of the registry in C:\Windows\System32\GroupPolicy and get merged into the registry during startup (for computer policies) or logon (for user policies). You need to view them as a separate entity which need not actually even exist for a setting to take effect.
When you view the local policy in gpedit.msc what you're viewing is what is in the C:\Windows\System32\GroupPolicy folder, not what's currently in the registry.
One suggestion would be to modify the local policy to taste on a test machine and drop the relevant files onto your other machines, but I haven't tested this and can't confirm it would work. Overall though I honestly think you're better off biting the bullet and putting Windows Domain Controllers in. You may be saving money on license fees with your current approach, but you're just losing a whole lot of time on maintaining an elaborate (and potentially delicate) setup that using Windows DCs would totally bypass. Unfortunately I suspect that the cost of the time you're losing would be multiples of the cost of just implementing Windows DCs.
Best Answer
Yes; from the Group Policy Object Editor, expand Computer Configuration > Windows Settings > Security Settings. You should see a Registry option, where you can add keys and specify permissions.
Note that just allows you to play with permissions; i.e. this is different from Group Policy Preferences, where you can actually set values