Ganged cutters is a classic. Old-school you'd use a fixture the length of your X travel with a quick clamping feature. Load up 15 or 30 parts, raise table, start spindle, cut in one pass, drop table, rapid reverse, stop spindle, unload, repeat. If you were serious about it, you'd make your fixture so the operator could unload/reload half the parts while the spindle was busy cutting the other half. Modern occupational safety guys would have heart attacks...
Besides ganged cutters, you should ask a couple more stamping companies. Make it clear you just need embossing or coining on one side, not full-depth bending or displacement of the part.
In addition to stamping, stuff like this is sometimes done with what you might call linear knurling. Cylindrical tool with V protrusions would be rolled over the part surface under substantial pressure. This was a job sometimes done on shapers if the volume didn't call for dedicated production equipment. Load a new part every stroke of the ram. 0.5mm depth on stainless might call for too much pressure, though.
