Originally Posted by Guessed

The only reason I can think of for this not to work on your machine is if you are using a non-English version of Word or Windows. Is that the case?

Try the same replace dialog with Wildcards turned off and
Find: ^p^p
Replace: ^p
This finds two consecutive returns and replaces it with one. You will need to do a Replace All multiple times because this halves the number of instances each time.