For sites where users are allowed to use HTML, the goal is not to escape the input, but to restrict what HTML features can be used.
The level of restriction depends on the site. A site like MySpace may decide to let users customize the appearance of their pages as much as they want. In contrast, a forum will probably limit users to P, BLOCKQUOTE, lists, simple inline styles, and perhaps images.
The naive approach of "stripping tags" using regular expressions often misses things because it interprets them differently than browsers do. For example, the regular expression <.*?> matches nothing in "<script src='http://evil.com/evil.js' </script", leaving your Internet Explorer and Firefox visitors vulnerable (see bug 226495 and for details about "half-tag" parsing). Gerv has an example involving unterminated entities. RSnake maintains an extensive list of XSS vectors that naive filtering may miss.
TODO: go through RSnake's list and make sure my advice covers everything.
The best approach is to parse the input HTML on the server, keeping only tags, attributes, and attribute values you want to allow. Upon serialization, the result will be "well-formed" HTML that browsers will parse the same way your server did.
Things you should ensure are never allowed in user-submitted HTML, to protect the accounts of visitors who use Firefox and IE:
If you must allow unsanitized, untrusted HTML to be part of your site, ensure that those pages are not on the same hostname as where other users log in. (webmail, web hosts, attachments in a bug-tracking system, Google cache) (see Gerv's proposal)
Content other than HTML and XSS
If you serve untrusted content as text/plain, be aware that some browsers will ignore the mime type (violating the HTTP spec) and treat it as something other than text/plain. Internet Explorer notoriously treats text/plain content as HTML if it contains anything that looks like a tag, and even Firefox does some sniffing if some of the bytes would be "control characters" in ASCII. The best solution is to treat untrusted text/plain in the same way as untrusted text/html that cannot be modified: serve it from a different hostname.