In this paper, we develop a novel algorithm that allows service consumer agents to automatically select and provision service provider agents for their workflows in highly dynamic and uncertain computational service economies. In contrast to existing work, our algorithm reasons explicitly about the impact of failures on the overall feasibility of a workflow, and it mitigates them by proactively provisioning multiple providers in parallel for particularly critical tasks and by explicitly planning for contingencies. Furthermore, our algorithm provisions only part of its workflow at any given time, in order to retain flexibility and to decrease the potential for missing negotiated service time slots. We show empirically that current approaches are unable to achieve a high utility in such uncertain and dynamic environments; whereas our algorithm consistently outperforms them over a range of environments. Specifically, our approach can achieve up to a 27-fold increase in utility and successfully completes most workflows within a strict deadline, even when the majority of providers do not honour their contracts.