Clustering is an effective strategy for tackling the dynamics and scalability in a large-scale mobile ad hoc networks (MANETs). However, the mobility of the nodes makes it very difficult to maintain the states of the clusters, such as connectivity between clusters, available bandwidth, and node membership. A good maintenance scheme should balance the workload and power consumption of the nodes, incur little overhead, and track the changes timely and accurately. For this, we consider the implementation of a maintenance sublayer to handle the dynamic state of the clusters. The idea is to hide the dynamics of the underlying clusters, to improve the performance of applications in MANET. In this paper, we examine the design space of the state maintenance problem in cluster-based MANETs. At one end, we study a fully distributed approach, called Cluster-Based WithOut Head Overlay (CWOHO). At the other end, we consider the strategy that uses cluster heads to handle the maintenance operations, called Cluster-Based With Head Overlay (CWHO). In-between two extremes, we investigate a third possibility, called Clusters with Neighbor Information (CNI). We provide an in-depth and comprehensive study of these strategies under various network conditions and mobility models. Our experimental evaluation shows that the data delivery ratio of CWOHO is at least 7% more than CWHO, under increasing node mobility and number of clusters. However, the reverse is true for the control overhead.