I haven't run across a problem like that related to a heading issue. Do your headings have lines or shading?
Does Set Alternate Text in the Accessibility tool point to headings?
No. The header levels are just Arial Bold. I did discover one thing though. If I convert the Word document from .docx to the old standard .doc, the issue resolves itself. When I looked in the old structure, all of those Header levels are showing up as images...included in the TOC.
I'm glad you were able to find a workaround. My best advice is to open a new document, copy the text from the original, paste it without formatting, then assign styles. It's more work on the front end, but avoids some of the funky stuff that can happen with an old document.
If I wasn't in a time crunch to complete updates and compliance checks on a number of documents, I might just do that; however, it just isn't feasible at the current time. I do think that there is something in the underlying transform process that is identifying a Heading as an image. It shouldn't be possible for it to make that error, but I am wondering if something got corrupted in the underlying XML.