Well, I strongly believe that every single line has a ^M at line end, then. Your script is changing the ^M^J (<CR><LF>) sequence to ^J^J (<LF><LF>) causing the extra line feed...
That's a bit difficult to believe - sed wouldn't substitute anything if no ^M char were present. At least it doesn't on my linux nor FreeBSD systems.
So - please post your OS and sed version, and a...