GNOME Evolution supports Markdown natively (I believe either raw or rendered to HTML on send; I use the latter.)