How can I run a Windows GUI application on as a service?

Windows services cannot have GUIs, so you will need to either get rid of the GUI or separate your application into two pieces - a service with no UI, and a "controller" application. If you have the source code, converting the non-GUI code into a service is easy - Visual Studio has a 'Windows Service' project type that takes care of the wrapping for you, and there is a simple walkthrough that shows you how to create a deployment project that will take care of installation.

If you opt for the second route and need to put some of the original GUI code into a controller, the controller and service can communicate via WCF, .NET Remoting or plain socket connections with a protocol you define yourself. If you use Remoting, be sure to use a "chunky" interface that transfers data with as few method invocations as possible - each call has a fair amount of overhead.

If the UI is fairly simple, you may be able to get away with using configuration files for input and log files or the Windows Event Log for output.

Has anyone used a third party product like: Always Up?

Seems to do what I need. It's the capability to keep running through login / logout cycles I need. And the capability to ignore that it's a GUI app and run it anyway.

They must be linking into the exe manually and calling WinMain or something.

You can wrap it up into srvany, though you may need to assign it an actual user account (as opposed to LocalService or some such)