We study the verification problem for e-service (and workflow) specifications, aiming at efficient techniques for guiding the construction of composite e-services to guarantee desired properties (e.g., deadlock avoidance, bounds on resource usage, response times). Based on previously proposed e-service frameworks such as AZTEC and e-FLow, decision flow language Vortex, and our early work on verifying Vortex specifications using model checking and infinite state verification tools, we introduce a very simple e-service model for our investigation of verification issues. We first show how three different model checking techniques are applied to verification of specifications in simple e-service model, where the number of processes is limited to a predetermined number. We then introduce pid quantified constraints, a new symbolic representation that can encode infinite system states, to verify systems with unbounded and dynamic process instantiations. We think that it is a versatile technique and more suitable for verification of e-service specifications. If this is combined with other techniques such as abstraction and widening, it is possible to solve a large category of interesting verification problems for e-services.