One thing that might help would be a very simple client-side trick: When somebody types a banned word, don't filter it on their side. This way, you see whatever you type, and unless you're talking with a friend via another medium (voice chat, etc), you're not likely to even know you're being filtered so people won't try to get around the filter (and won't know without help or multiple accounts whether they were successfull).
Then, instead of removing the word for other people, simply replace with with a random unlikely-to-ever-be-inappropriate word. For added humor, select words like "fluffy", "shiny", "pretty", "clown", "flower" etc
As for the method to use, I would use a three-table approach: First is a table of character transformations that turns "$" into "S", "@" into "a" etc; Second is a table that performs letter-group replacements in an attempt to account for typos, misspellings, etc; Third is a list of banned words.
Using the first two tables, you can generate a list of possibilities for each word, and you can then check the dictionary to see if the word is present or not.
You might want to employ phonetic algorithms, such as
Double Metaphone, as another dictionary to detect misspellings that allow the same or similar pronunciation.
A more fullproof method would be to simply have a 'white list' instead of a 'blacklist' - a filter based on allowing only specific words. If you can find a fairly complete wordlist, you can combine it with a name list based on census data and then the only thing missing is fictional names / places / etc that you can add manually as desired.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
