You should make sure whatever solution you finally end up choosing can beat the XSS Cheat Sheet. That will require testing in a lot of different browsers on a lot of different machines.
You should also seriously ask these questions:
Do the users really need any markup at all?
If they do, does it have to be HTML?
If they do, can it be a very limited set of tags?
You may find that you'll be able to choose a simpler means of filtering depending on your answers.