Cloud services are often distributed across several data centers requiring new scalable approaches to efficiently perform searching to reduce the energy and price cost of fulfilling requests. Multiagent-based systems have arisen as a powerful technique for improving distributed processing on a wide scale, which can operate in environments where partial observability is the norm and the cost of prolonged search can be exponential. In this paper, we present a multiagent-based service composition approach, using agent-matchmakers and agent-representatives, for the efficient retrieval of distributed services and propagation of information within the agent network to reduce the amount of brute-force search. Our extensive simulation results indicate that by introducing localised agent-based memory searches, the amount of actions (with their associated energy costs) can be reduced by over 50% which results in a lower energy cost per composition request.