PDF wanders off to a random location when finding/searching for something on the document

I am using Adobe Acrobat Reader DC. Everytime I search for something on the document, the word gets correctly highlighted, but the location is not correct. It takes me to a random location on the document. I have tried purging the cache as well as unchecking fast searches - but still the same issue.

However, when I open it in Mac preview, the search works just fine. Not quite sure whats happening here.

I have tried this in both Mac and Windows and I see the same behavior on both.