Perhaps there is something wrong with your system.

I just created a document containing 375 pages (7306 paragraphs) of your sample text, then did a Find/Replace with:
Find = ^p^p
Replace = ^p
The process took about 1 second to complete. Even creating said document was a breeze.

As designed, Word can handle documents up to 512Mb in size, including 32Mb of text.

__________________
Cheers,
Paul Edstein
[Fmr MS MVP - Word]