BACKGROUND: The effectiveness of malaria vector control interventions is often evaluated using cluster randomized trials (CRT) with outcomes assessed using repeated cross-sectional surveys. A key requirement for appropriate design and analysis of longitudinal CRTs is accounting for the intra-cluster correlation coefficient (ICC). In addition to exchangeable correlation (constant ICC over time), correlation structures proposed for longitudinal CRT are block exchangeable (allows a different within- and between-period ICC) and exponential decay (allows between-period ICC to decay exponentially). More flexible correlation structures are available in statistical software packages and, although not formally proposed for longitudinal CRTs, may offer some advantages. Our objectives were to empirically explore the impact of these correlation structures on treatment effect inferences, identify gaps in the methodological literature, and make practical recommendations. METHODS: We obtained data from a parallel-arm CRT conducted in Tanzania to compare four different types of insecticide-treated bed-nets. Malaria prevalence was assessed in cross-sectional surveys of 45 households in each of 84 villages at baseline, 12-, 18- and 24-months post-randomization. We re-analyzed the data using mixed-effects logistic regression according to a prespecified analysis plan but under five different correlation structures as well as a robust variance estimator under exchangeable correlation and compared the estimated correlations and treatment effects. A proof-of-concept simulation was conducted to explore general conclusions. RESULTS: The estimated correlation structures varied substantially across different models. The unstructured model was the best-fitting model based on information criteria. Although point estimates and confidence intervals for the treatment effect were similar, allowing for more flexible correlation structures led to different conclusions based on statistical significance. Use of robust variance estimators generally led to wider confidence intervals. Simulation results showed that under-specification can lead to coverage probabilities much lower than nominal levels, but over-specification is more likely to maintain nominal coverage. CONCLUSION: More flexible correlation structures should not be ruled out in longitudinal CRTs. This may be particularly important in malaria trials where outcomes may fluctuate over time. In the absence of robust methods for selecting the best-fitting correlation structure, researchers should examine sensitivity of results to different assumptions about the ICC and consider robust variance estimators.