When sending HTML mail in OL2003, the recipient always seems to get my
messages with an extra line between each paragraph. However, this extra line
does not show up at my end (e.g. when looking at the sent messages folder).

What do I need to adjust to fix this?

Under Tools | Options, I have 'remove extra line break...' checked - but
that of course applies to Plain Text Messages.