So what I ended up doing - which sort of solved the problem - was select the entire mesh's verts, then go to "Mesh Display > Set to Face" to flip the vert's normals. Every time I encountered this problem I did that and it looked fine for a while.
I don't know if that's the best answer, but if anyone else encounters this problem you can try that.