I want a new unique online identity - how to find one?

I want to start a new online identity and use a single common identifier on as many sites as possible. What web apps or other methods are available for me to check if my proposed nickname is already in use? I definitely want to avoid any service that might start cybersquatting on the name, if any are suspected of doing that.

Edit: agreed, this does make my online presence very searchable, and I'll give that some more thought.

From web app William

• namechk.com will check 149 sites (although some don't seem to work). The check is done on the client-side using JavaScript, so name squatting is not easily possible.

  William : Nice one, neo. Thanks for that.
  From neo

• Long time ago I started to use couple of random letters (Fczbkk) as my nickname. So far it was everywhere I tried to register. Even my domain (http://fczbkk.com) was free. Choosing "Fczbkk" was one of the best decisions I have ever made.

  So if you just need an unique identifier for your on-line identity, I'd recommend using any random generator. Or you can smash your forehead against the keyboard or something like that.

  William : This is an interesting idea. I was hoping to use something less random but this method is growing on me. I am going to try bashing my head on the keys shortly :D

  Benjol : IIRC, this was how xkcd was born too.

  Julien N : Good idea, and you can choose random letters and then try to give it any meaning. Could result in something quite fun !

  Andrew : On http://reddit.com it's pretty common to create usernames after CAPTCHAs new users get on registration

  Evan Plaice : @Benjol Here's the reference http://www.youtube.com/watch?v=zJOS0sV2a24 @ 44:30

  Andreas : +1 for "forhead against the keyboard" - as if 20 times per day isn't enough
  From Fczbkk

• Similar to namechk.com mentioned by @neo, knowem.com will search 150-300 sites for free, and will register them for you if you pay for their premium service.

  William : Thanks, this is a great choice too. I like the way they divide sites into topics.
  From 3rdparty

• There used to be a website that would make pronounceable passwords for you. You could specify the beginning or end, etc. I used part of the street I lived on and had it generated the rest. I've used Postagulous on many forums and sites.

  The downside is that you are terribly searchable. Horribly so.

  ZoFreX : Tell me about it... the amount of trouble I've gotten into :/

  Satanicpuppy : @ZoFrex: The secret is to be secret. I'm horribly searchable, but my most common online identity isn't associated with my actual name.

  ZoFreX : It wasn't super-easy to link my identities, but my friends knew, and that's enough to get you in trouble if they read bash.org.
  From Postagulous

• I made anagrams out of my favourite things until I found one that wasn't taken!

  BarrettJ : Zoloft, Fresca, and Xtacy?

  ZoFreX : FZeroX. But close!
  From ZoFreX

• I like plain old Google. Google your proposed name, and the fewer hits the better. Then trademark it, and SUE SUE SUE! (Heh).

  From Satanicpuppy

• Also, another option is namechecklist.com which will tell you domain availability and search engine rankings as well.

  Its not as comprehensive on the social media part, but it is quite elegant.

  From 3rdparty