The problem I see with allowing HTML is that you're opening up your server to being hacked. A person who can embed HTML in their messages can take over your server, or do things with the privileges of other users.
You can get around this, but it is tricky. The ideal solution, I think, is using something like:
http://www.aaronsw.com/2002/atx/intro
or a Wiki-style markup instead of HTML