It seems that Network Solutions (one of the leading domain registrars) is doing something nasty with the their domain availability facility on their site:
* When you search for a domain name to see if it is available on their site, and if it is not yet registered, they reply "No, not yet registered".
* A few seconds/minutes later, you go to another registrar to buy the domain.
* Bad surprise, it is no more available. It was registered by Network Solutions!
Actually, you can still get it but from Network Solutions only. If you don't want to get it from them, you'll have to wait 4 or 5 days until they release it.
For more information, please refer to
http://slashdot.org/articles/08/01/08/1920215.shtml .