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.
Have you checked your eventvwr logs? Do you have other Domain Controllers (DCs) in this domain? Which one is the Global Catalog (GC) FSMO? Try running
dcdiag.exe
and check the output for problems, especially with the SYSVOL and/or replication with other DCs.
THIS CAN BE DANGEROUS: If this is not the only DC in the directory, and the event logs don't reveal anything, try making a copy of the sysvol\domain\policies and place it elsewhere on the hard drive of the server. Make sure you do this during off hours and make sure you perform a complete AD backup using:
ntbackup.exe backup systemstate /J "pre-delete-ad-backup" /F "c:\adbackups\ForestBackup.bkf" /V:yes /M normal
Copy the ForestBackup.bkf off of the server after the backup is complete.
After you create the backup and copy it elsewhere, delete the sysvol\domain\policies directory. Then force a replication with another DC in the Directory using replmon.exe
Check the FRS eventlog and see if you get messages about a successful sysvol replication. Keep in mind that until Sysvol is restored in complete, your server will not be able act as a DC, so make sure that another DC is available to your clients...
Best Answer
Policies don't really apply to services because they don't have an interactive login. There are exception like a password policy, but that is because the policy is actually being applied to the DC.
My guess is you have logged into the server at some point with the OLD credential, and that is why there is a profile and a policy applied to that profile.
If your needing the service to use specific networking settings, you will need to apply those settings to the actual server since a service login normally does not have a full profile established for it.