TME,
Your solution of coring then percussion re-drill would work. Doubles the work, but reaming the hole with a percussion bit works.
Back about 15 years ago we did a repair project where the general contractor installed 160 each x 1-1/4" dia anchor bolts x 6 feet long into a large octagonal-shaped concrete pedestal for a 150' high steel chimney stack for a power plant. Unfortunately they PAINTED the embedded anchor bolt length (straight shaft). It was in a typhoon region so wind loads were significant.
We load tested the installed bolts and they slipped out at about 10% of required capacity.
Long story, short. We removed the AB's (that was relatively easy) then core drilled each hole to slightly over-size the resulting hole, then ACID ETCHED the hole, neutralized the acid, checked the pH to make sure it was alkaline, then installed the sand-blasted AB's, then epoxy injected the annular space, then load tested after cure.
We also did some trials on non-etched holes (just core drilled) and they also tested to the same magnitude as those that were etched. BUT - the holes were cleaned repeatedly to remove the coring slurry. The slurry, if not removed immediately, causes significant loss of bond.