I recently saw this clip where Karl Pilkington visits a Vanuatu tribe, in which it is said that every word of the Ninde language begins with the letter 'n'. I soon called BS, and as the wiki-page I linked to confirms, it was. My reason for doing so is that I'd think that if there was a language where every word began with an 'n', the speakers wouldn't be able to infer any information from it, and it would surely be dropped.
My question is whether or not this gut feeling is actually true: Has there ever been observed a (natural) language where some rule that in principle carried no information was still used?