Today I was walking along a honeylocust tree that shows similar damage to that of an emerald ash borer insect. So far is "hasn't" been reported here yet, but only when is the question. Ash trees here are mostly located in the older neighborhoods and such. Now this honey locust seemed to have the "D" shaped holes and the inner cambium beneath the bark look gobbled (exactly in "S" shapes like the emerald borer) up by some critter. I've googled so far and no similar results have shown. So maybe it's adapted to locusts now?
There are a lot of native tree borers out there, but they don't get the press like the Emerald Ash Borer. There's the bronze birch borer that leaves D-shaped holes and the locust borer that feeds on black locust. Since you were looking at a honey locust tree, my guess would be that you were seeing damage from a Honey Locust Borer.