Ehh... just go with HTML, and sanitize it.

Markdown and all those alternate formats are convenient when you consciously know you're using them, but none of them can agree on how to specify anything, and in the end they just end up confusing people. What's bold again? Asterisk? Two asterisks? Three apostrophes maybe? Or was it double underline? Not to mention the frequency of mangled posts by people who weren't expecting their text to be formatted at all. And even if you spell it out exactly how to format their posts, people often don't read any of that stuff. One of the most difficult-to-accomplish parts of software design is getting things to do what people expect without requiring them to read stuff first.

IMO plain, unadorned text should be the default, at the most linking links and >>1s and highlighting > quotes. None of those mangle existing characters and any unintentional formatting is unlikely to alter the meaning of the message. If you want more, put them in a dropdown like kareha does, so people can use what they're familiar with.