Cut-elimination for calculus with nats or other inductive datatype?
How about Ulrich Berger's work? For example Strong normalization for applied lambda calculi. The "recursively defined constants" part gets you inductive types, more or less. And don't be put off by the word "untyped", he gets results for typed systems too.