If the movie theater also restricted your right to write a negative review afterwards, say, it would be a bit dicey.

Some contracts that suppress rights might be defensible BUT the point is that such contract are not apriori valid.

Indeed, your the military example shows the need for limits; there's a reason that only the state can operate with the contract you describe. If a private organization could do such a thing, there would serious trouble on many fronts (private armies = bad things).