I believe this is due to the offending elements not being part of any actual page.
What I mean by this, is that the elements may exist in the PDF, but they aren't actually connected to any page. So you will never be able to find them, and when you search a specific range of pages (as long as it's not the whole range), Acrobat X won't find the element. (If you search the whole range, it just conflates that with the whole document, and searches everything.*)
*I know this by trial and error.
"I believe this is due to the offending elements not being part of any actual page."
On point. More specifically, tags are independent of PDF page content.
This is why "walking" the structure tree can be important.
For those who need to or desire to provide accessible PDF the pending release of the following documents will be "must have" references.
--| The ISO Standard for PDF/UA (ISO 14289-1
--| PDF/UA-1 Technical Implementation Guide
--| PDF/UA-1 Technical Implementation Guide: 32000-1
(ISO 32000-1 is the current ISO Standard for PDF)
--| Achieving WCAG 2.0 with PDF/UA
(WCAG 2.0 for PDF is PDF/UA)
The latter three documents are expected to be available on AIIM's web site.