PS PagePlus will search and replace text on every page of the file, if you ask it to... However, once you're at this point, you are searching the text of the temporary ppp file, not the pdf. Nuance PDF Converter Professional 5, on the other hand, will search for text over the entire document but doesn't seem to offer a batch replace feature. The search feature returns a list of linked occurrences of the text and you need to replace each occurrence individually. I *may* be wrong about this, but if there is a more robust/convenient "search and replace" feature it's very well hidden

@Curt - PagePlus will search and replace the entire document in a single search. PDF Converter Pro will search the entire document in a single search.