The provisioning of Ambient Services is gaining importance as users become more and more embedded in environments that are saturated with electronic devices. In our previous work, we have proposed the Ad hoc Service Grid (ASG) approach as a means for deliberately setting up an infrastructure for providing Ambient Services at medium-sized locations like shopping malls. In this paper, we introduce a self-repairing Lookup Service architecture that is able to handle dynamic services in an AGS. These services can autonomously replicate and migrate within an ASG to optimize resource usage and message latency. Our Lookup Service is able to cope with the inconsistencies caused by service migrations efficiently by applying a lazy, request-driven update protocol. We discuss the architecture and the protocols employed by the Lookup Service. Moreover, we provide experimental results that show the efficiency and effectiveness of our approach.