I assume your goal is to automate what is now a pretty much manual process?
Typically internal keyways are cut with on-size tooling. -0.000/+0.001 seems about right on the smaller sizes, but maybe a bit tight on the larger sizes. A blind hole adds another layer of complication to the mix, but you must have that well under control.
I really don't think a VMC is the best tool for the job. While it could be made to work with the right tooling, finding one with about 40 inches of Z clearance might be a little difficult, at least until you get into some really big machines. What might work well as a base machine is a small metal planer (moving table) or perhaps a huge shaper (moving ram), maybe 1930-50's vintage. Then add some CNC functionality to it. As much as I hate hydraulics, a hydraulic ram might make the most sense for this application.
Using carbide insert tooling shouldn't really be a problem, it would just require the proper insert and holder geometry. You would most likely need to build your own tool holder for the insert. I would think any just about any rectangular insert would work. A SNMG 431 insert might work for most of your work.