Check if a service exists on a particular machine without using exception handling

You can use the ServiceController.GetServices() method to get all of the services on the machine, then look through them to see if one exists named what you are looking for:

bool DoesServiceExist(string serviceName, string machineName)
{
    ServiceController[] services = ServiceController.GetServices(machineName);
    var service = services.FirstOrDefault(s => s.ServiceName == serviceName);
    return service != null;
}

The FirstOrDefault() extension method (from System.Linq) will return either the first service with the given name, or a null if there is no match.

To address your speed issue:

The difference between the two approaches for a single method call is negligible, regardless of whether the service is found or not. It will only be a problem if you are calling this method thousands of times—in which case get the list of services once and remember it.