Having worked with feature flags "at scale" (whatever that means :), here's some advice that I've learned from working with hundreds of developers across tens of teams and given to others. I'm leaving out experimental analysis (A/B testing, multi-armed bandit) because it just adds "...but consider how this affects your metrics".
* Always be developing against the current running features. No brainer.
* Design things so that they integrate feature flags, not work around them. This usually means pushing feature flag determination to more generic/common code.
* Separate backend/frontend changes into separate feature flags when possible. Turn on backend changes early and often to better measure your feature's impact.
* Give individual features their own flag, but also have a global flag that manages the entire experience. This makes it easier to manage your gradual dial up as well as shut off problematic features that would otherwise mess up the launch.
* Be diligent about removing feature flags once they're turned on. Schedule it into sprint time, reward teams that remove them, make it a management mandate, whatever. Just get rid of them once they're no longer needed.
* Invest in monitoring around your services that (ideally) can correlate failures with features. you should turn on features over the course of a few hours/days to mitigate customer impact in the event of failures and gain data about performance at 50/50.
I think the answer to your specific question of "testing every combination" is that you can't, easily. But by keeping the number of feature flags that are inactive low (< 150 is very liberal) for a given service, having everyone develop against the current running features + dev overrides, and using gradual dial up with integrated monitoring to catch poor interactions when the impact is small, you'll have mitigated a lot of your concerns.
