You don't need to test every permutation. Pretty much all of the flags in the codebase are independent of each other - someone might be working on changes to our admin interface in some files while someone else is changing the way comments are displayed elsewhere. There's no overlap in the changes.
If the flags do interact with each other then in most cases the features will launch one after another, so you only need to test a handful of states (foo off bar off, foo on bar off, foo on bar on)
If the flags interact with each other and the features will be launching at the same time (or the betas overlap) then you have to do the same amount of integration testing that you'd have to do with landing several branches into trunk at once. This is complex, we don't do it very often.
And we clean up flags once they're not needed any more, which minimizes the possible combinations.
I was skeptical about this before I started working at flickr, now I can't imagine working any other way.