I am quite opposed to supporting underlined text without semantic meaning. For the same reason that Markdown does not support fonts, colours, and other presentational features. We have CSS for that. @mofosyne, word processors could potentially use a Markdown + CSS combination.
<mark> and <s> are interesting. I’ve personally never used either. It would be good to see a real need for these before extending the Markdown syntax.