This paper presents planning-based service composition algorithms that dynamically interact with a potentially large-scale directory of service advertisements in order to retrieve matching service advertisements on demand. We start with a simple algorithm for untyped services, similar to a STRIPS planner. This algorithm is refined in two steps, first to exploit type information, and second to support partial type matches. An evaluation confirms that the algorithms scale well with increasing size of the directory and that the support for partial type matches is essential to achieve a low failure rate.