You could try exporting the documents to Wordperfect for DOS (or possibly the Windoze version). It's cabable of doing a search & replace through the whole of the document. At least v5.x since that was the one I've used used the most although I'd be surprised if v4.x can't do it as well.
I know Word 97 can export/import WP formats.