Wire EDM would be much more readily available, I'd think. Afterwards you can sand/polish the edges with a belt. No worry about heat treat because the operation takes place underwater.

We've got a CNC EDM here at work and it's not in use most of the time, but I don't know how to run it and can't offer it up for you.