Mage accuracy is based off int and luk (contributing the same, so even for acc adding luk doesn't really help), but mages tend to be very heavily punished for being under leveled, at low levels (high lv you just naturally have enough magic acc to not care). The acc value shown is your physical damage accuracy, not magic accuracy. Accuracy stat is physical, not magical iirc. The damage comment was because grinding with low level heal just kind of sucks in general, not related to magic acc in particular.
