So for your product to be competitive, it needs to be very compelling to get over that hurdle, and be much superior to anything else. Being in `magic quadrant` in Gartner or other is also useful (yes I know, it does not mean much, but it looks good for management).
One common way of getting over that hurdle is to find a creative way for your service to move to the capex side of things. One example is selling an appliance which does not do much, and relies entirely on your service, sell it for a very high price, bundle a 3 year support contract that covers the cost of your service, and suddenly it's capex :-)