I'm just gonna give a few impressions on what I've think from my experience..
Never ran a Makino. Have always heard good things about them though. Built like tanks, but very expensive.
We used to have a Mitsubishi FA30. It's the worst machine we ever owned. The threader was terrible, the control was counter-intuitive, and it couldn't cut parts over 12" (This thing had a 20" Z axis) with nothing less than an .006" bow in the middle of the cut, no matter what I did with the technology. When I questioned why this happened, I was told the power supply wasn't big enough for that machine, and we should have bought the higher model Mitsubishi with the bigger power supply. Take that as you will. Again, this is just my experience, your mileage may vary.
We have 2 older Charmilles machines, a 290 and a 510. They're rock solid, and don't break down much. Excellent for 4 axis cutting, and do well on tall cuts. Can't say much about the threaders as ours don't have them. Controls are very nice. As you said, support can definitely be a little spotty sometimes, and parts are very expensive. Luckily ours don't break too often.
We have 3 Fanucs, an Alpha 0B, an Alpha 0C, and an Alpha 1iD. I love these machines. The control is awesome, very intuitive. Extremely accurate with good finishes. Support has always been good to us, and parts aren't particularly expensive. The threader, especially on the new 1iD, is incredible. From a wire break to a rethread and back to burning it's something like 10 seconds, and can usually rethread in the kerf, depending on cutting conditions. I would say you should definitely look into a Fanuc, especially if you're very concerned about threader performance. These machines have won me over and I would happily replace almost any machine in our shop with one.