In systems with frustration, the critical slowing down of the dynamics severely impedes the numerical study of phase transitions for even the simplest of lattice models. In order to help sidestep the gelation-like sluggishness, a clearer understanding of the underlying physics is needed. Here, we first obtain generic insight into that phenomenon by studying one-dimensional and Bethe lattice versions of a schematic frustrated model, the axial next-nearest neighbor Ising (ANNNI) model. Based on these findings, we formulate two cluster algorithms that speed up the simulations of the ANNNI model on a 2D square lattice. Although these schemes do not eliminate the critical slowing own, speed-ups of factors up to 40 are achieved in some regimes.