How soon do Mages become able to hit Headless Horseman

Well, since you're a cleric, you won't be doing any decent damage to bigfoot anyways. Against horseman, I'd say you'll be getting 100% accuracy around level 105. Search for the accuracy formula.