Well it's not just down to protein. Gongys like flying food because it's what they're adapted to catch, but the flying insects (it is my understanding) such as the fly, wasp, moth etc, all also contain more sugars, also flight muscles (that are actually used for mobility, not just evasion), very nutritious, yum yum. If 'it'll just poo more', then maybe the food had too higher ratio of protein (or otherwise) over the other ingredients? If a mantis is getting a whole ton of protein (or any animal for that matter) but not much of the other important stuff, then it's out of balance and not healthy.
Dave