The interaction of flexible free-to-move boundaries with non-Newtonian (complex) fluids is receiving increased attention. Accurately capturing the coupled dynamics of this intricate flow-structure interaction is a challenging computational problem. The Immersed Boundary (IB) Method provides a versatile tool for this type of systems. However, even in the Newtonian fluid case, strong tangential forces on the immersed structures induce a well-known, severe time-step restriction for explicit discretizations. Moreover, as the number of immersed elements increases, the direct evaluation of the flow-structure interaction becomes computationally expensive.