What type filament should I use to produce stamps?
I see three options...

1. Print with a flexible filament:


Many options: TPU as you pointed out, the flexible PLA that Tom mentioned, and others.  Here's an article with a few options from Matter Hackers
I'd suggest printing the stamp side down so you get a nice flat stamp with no post processing.  For any wide gaps, mind your bridging...use fillets or chamfers so the "roof" of the gap is an upside down V or U shape.


2. Print with any hard filament, but use a rubber mat under the paper.


The idea here is to use a semi-flexible surface under the paper to help get uniform contact pressure between the paper and the hard stamp.  As long as your stamp holds ink, this should work okay.


3. Print your stamp shape, then use it to make a rubber stamp.


Making a model and then copying it with your desired non-printable material is a common manufacturing technique that can be used in many situations.  Use of molds for casting and related processes can really expand your possibilities.  Check out Smooth On.  They have several rubber and flexible compounds that you could use for stamps.