It's natural -- responsible, even -- to consider the "what if" any time you're introducing a new dependency on a service. You may not consider it consciously, but even the most reliable services we use fail us sometimes. It would seem impossible not to develop this sense at some level.
> Conventional wisdom says that reliable services that are always online would be perceived as being more trustworthy than those which go down.
That's not conventional wisdom, it's naivety. 100% reliability doesn't exist over any significant time scale, thus the assertion of this particular "conventional wisdom" is a wisdom that no one has developed. If it is anything, it is a conventional misconception. We might tell ourselves this with our consious minds, but we are all weary of the risk of failure at some level.
* All services have outages. Customers know this, even if they express otherwise.
* Prior to an outage with a new service, responsiveness to outages is an unknown to customers. Uncertainty is a common source of anxiety, resulting in dissatisfaction.
* After a provider has responded positively to an outage, the uncertainty is alleviated, leaving the consumer with a greater sense of confidence. Remember, the consumer knows that regardless of provider, they run the risk of experiencing an outage, so this confidence becomes an anchor.
The tipping point is when frequent outages outweight the benefit of certainty. There comes a point at which your customer deems you to be incompetent, despite the hustle you exhibit in the face of a failure.