Make a practice document and see if Search and Replace hyperlinks works in it, which you should be able to do so

If it does, I would Cut and Paste Special the old contents in the document (in question that is NOT allowing you to Search and Replace) into a new document

Note, Use Paste Special, select Unformatted, so if there is garbage in the original document this will NOT get transferred over