MANETs are self-organizing infrastructure-less networks formed on the fly by a group of wireless nodes. The lack of central administration in these networks necessitates host auto-configuration. The proposed auto-configuration protocols to date are either not robust enough to respond efficiently to the dynamic nature of the MANETs or they are resource greedy. Also, there has been no detailed attempt made to compare the effectiveness of these protocols which is essential to judge relative merits and demerits. This paper presents a new stateful robust host auto-configuration protocol which is based on dynamically selected Address Agents (AAs) that maintain a distributed address table. The performance of the proposed protocol is comprehensively compared with a representative protocol that employs a different address table management technique.