Composition of web services has received much interest to support business-to-business and enterprise application integration in the field of e-Commerce. Current web service composition approaches range from practical languages aspiring to become industrial standards (like BPEL, WS-CDL, OWL-S and WSMO) to theoretical models (like automata, Petri nets and process algebras). In this paper we compare these approaches w.r.t. a carefully selected set of characteristics (like trust, security, performance and scalability) and we advocate the use of formal models, and their tool support, to increase one's confidence in web service compositions. This paper can assist web service composition designers and developers to deliver lasting solutions, in concordance with the technology's critical needs.