Generating addresses starting with certain characters such as "JoeAnonymousUserB7pMqyVa8JRcpZdCQLQ"
Yes, the concept is known, and called "vanity address". The problem with it is that it takes a lot of computing power. However, there is also a "split-key" method of generating vanity addresses, which lets you commission other people for the computing work. And finally, I created a website called Vanity Pool that handles a sort of free market of vanity miners and buyers.

As for the legal issues, I have already included a so called "illegal number" in the block chain as a part of my master thesis. So far Bitcoin hasn't been banned;).