The UAC in Vista and later is designed to prevent even administrator accounts from doing "dangerous" things without user confirmation. Running as Administrator alone is not sufficient to avoid the prompt as Microsoft has tried very hard to ensure that the prompts cannot be worked around. (This is so that virus authors can't go that route.)
The "right" way to handle this is to ship a manifest that tells Windows that an application needs elevation. It will ask for it on launch. If there is no manifest, Windows tries to figure out which applications require elevation (for example, an installer named "setup.exe") and request elevation from the user on launch. It is very frequently wrong and this results in cascade of errors later on.
I agree with you that disabling UAC entirely on a machine is the wrong approach. I'm no fan of UAC, but it is the world Microsoft wants us to live in. None of them really get rid of the UAC prompt, they just get the user's permission at some more convenient point in the launch process. (I realize not all of these apply to your situation:)
Number one recommendation: avoid tasks that Microsoft considers "dangerous". Sometimes elevation is unavoidable but other times it is the result of using deprecated Windows programming techniques like writing a config file to the %ProgramFiles% directory. In these cases I recommend capitulation to the Borg; if Microsoft wants you to write to %AllUserProfile% instead of %ProgramFiles%, just give in and change it. I recommend testing the application in a regular (non-Administrative) user to see where the problems are.
If you just want to do a simple SysExec call and you don't mind getting the prompt (i.e. it needs to work, but it doesn't need to work unattended), you can use John Robbins' elevate.exe to run the command (sc start or whatever) with elevation. We use elevate.exe in our installer batch file; the user clicks through one UAC prompt which elevates the batch file that runs multiple installers. (Johannes Passing wrote a version of elevate.exe in regular C; I haven't tried it.)
Run your application as a service. Microsoft believes that applications that run unattended should be services. A service running in a privileged account (i.e. LocalSystem) can perform tasks that require elevation without any dialog boxes. The thought here is that since UAC elevation is required to install the service no further prompts are needed. This is how our production application runs. We use FireDaemon to do this and it is quite easy to convert your LV app to a service this way. (There is also the free "srvany.exe" application from Microsoft floating around.) There are other advantages to running as a service, such as automatic restarts when the application quits or crashes. There is, unfortunately, a winkle running an app as a service under Windows 7: starting with Vista, Microsoft no longer allows services to have user interfaces. (This is another security "feature".) Thus to go this route you will have split the functional part of your application from your UI. It's quite doable (especially if you use the VI Server) but if your application has a lot of UI this might be an untenable amount of work. I suppose you could go the other way and have a lightweight helper service that performs just a few tasks that require elevation under the command of your main app. That would be pretty easy.
Have your application request elevation on startup. This is the method Microsoft wants you to take. (Well, not really: they want you to have buttons all over the place with little shield logos that only request elevation on the specific tasks that really require elevation.) You can request elevation by embedding a manifest in the application. This is supported by the LV Application Builder, although documentation is extremely sparse. See this PowerPoint presentation on how to construct the manifest.
While you are at it, digitally signing the application will avoid another bunch of UAC warnings on installation and launch. You can use self-signed certificate or a "real" certificate backed up by Verisign etc. "Real" certificates cost money but provide traceability. Signing your code shows that your application hasn't been modified since your released it.
While we are talking Windows 7, keep in mind that the Program Files directory is now called Program Files (x86) when 32-bit LV is running on a 64-bit versions of windows. So make sure to clean out those hard-coded paths!