You need to first replace double line breaks with, say, __PARAGRAPH__ text. Then remove all single line breaks. Then replace the _PARAGRAPH__ text with double line break or however you want to seperate two paragraphs.
That would certainly work, if there were actually double line breaks where the paragraph breaks should be. Unfortunately there are just single line breaks in all instances, so there is no way to tell where a break should be and where the text should just wrap round.
I thought Notepad couldn't handle special character sets? I shall have another play with it.