In the original service-oriented view of software provision, loosely-coupled services are brought together at the time of need and unbound immediately following execution, allowing service procurers to focus on selecting services that best correspond to their evolving requirements. This just-in-time approach requires the assessment of quality properties of both the software and the service provision activity in order to judge candidate services. In this paper, we propose and evaluate a multi-perspective quality evaluation model tuned to the needs of this "just-in-time" service provision vision. The proposed model uses a hierarchal structure of the quality features that characterize both the software and its provision arrangements from the perspectives of different stakeholders in the service provisioning and consumption process. The development and evaluation reported here took place in two phases: a "role playing" user study involving 15 participants to elicit the suitability, applicability and measurability of quality characteristics; and a contextual interview involving 24 users (12 software professionals and 12 general users) to uncover their mental models towards quality and evaluate the resultant characteristics identified from the first study. Our findings were twofold. Firstly, we show that a broader range of considerations encompassing both service quality and quality of service must be accounted for when dealing with software services (e.g. service functionality and service responsiveness). Secondly, we identify and explore the users' mental model of quality within the service-oriented paradigm.