GoogleもYSTも最近のロボット型検索エンジンはWebページ収集を勝手に行うため、ウェブサイト運営者側があえて"URL登録"の手続きをしなくとも待てばよくなっています。クローラがリンクを辿ってWebページを発見、登録していきますから外部からリンクを張られる - 例えばトピックで関連のあるページや、Yahoo!やDMOZといったディレクトリへの登録 - ことにより検索エンジンに登録され検索可能になります。
しかし時として、どんなに待っても全く登録されない場合もあります。この場合原因特定が困難になるのですが、米WebmasterWorldに「Googlebotがクロール出来ない」事例が出ていました。
I doubt that this problem is user-agent based; the issue appears to be just for your webhost and just from known-Googlebot IP ranges. PatrickDeese, is your site hosted by BlueGravity? I asked someone from our crawl team to try crawling from a known-Googlebot IP vs. a not-as-well-known Googlebot IP. The known-as-a-crawler IP couldn't fetch your pages but the not-well-known-as-Googlebot IP could, which does lend support to your hypothesis. [GoogleGuy / Website Technology Issues / WebmasterWorld]
GoogleGuyによると、この相談者(Googleからサイトが消えちゃったと書き込みした人)のサイトがホストされているサーバへクロールを試みたところ、一般には知られていないIPアドレスを持つGooglebotならクロールできるのに、一般に知られているIPアドレスを持つGooglebotではクロールができなかったそうです。
Googlebotがクロールできないサーバに設置されているページは当然Googleに登録されるはずがありません。おそらくホスティング会社側の設定ミスによりGooglebotのIPアドレスを拒否してしまっているのでしょうが、サイト運営者も困ってしまいますね。他のサーバに移転するしかありません。
ちなみに、色々なクライアントを見ているとごく希にGoogleに全く登録されないサイトを扱うことがあるのですが、大抵はサーバを変更(ホスティング会社を他に変更)すると解決してしまうことが少なくありません。