Well, it took me a while - but eventually I addressed the issue: UAC. I hate that addition to windows, and by default I disable it whenever I can. That being said - many users don't. And any application that attempts access to the registry flops miserably.
So while reading a recent positive review of DelayedExec I decided to finally take some action.
The solution was very easy and is demonstrated here.
To download, enter the application's page at my blog: Download DelayedExec.
I might add that I've just installed Windows 7 on one of my home PC-s, the one clunker which made me think of creating DelayedExec to begin with, and Windows 7 kicks ass. It fixes the windows startup sequence in particular. No it still doesn't let you choose a sequence and order, but Windows doesn't 'hang and die' while it tries to run everything at once on startup. I suspect it has more to do with services and internal windows lock mechanism finally doing what they're supposed to....