How many pieces are you talking about here? For production quantities I would look at broaching. For small batch quantities, EDM will be more cost-effective. As to EDM, you can hold 0.0001's (inches) depending on the time you're willing to put into the process and the surface finish you want.
Cost detractors to broaching: machine costs and specialty broaches. That hardness is going to be hell on the cutting edges long term (e.g. production quantities).
Cost detractors to EDM: machine costs and the cost of graphite for electrodes (if using a sinker). Wire costs aren't bad if you can cut straight thru (wire EDM). It all depends on what the part looks like.
You'll also want to look at how difficult the fixturing of the piece may be. Is the shaft long, part of a sub-assembly, etc.? That will affect your tank size, and thus potentially the shop that can burn the piece for you.