Hello!
There are a few possibilities that may be happening here, for
sure. You could do a check whether the same domain name was used
before and let go, perhaps it did some big no-no's.
Is the site using "frames" that can have a bad effect of listings.
Has the site been around for more than a few months, it takes
time to get listed.
What search engines are you using to find ther site? Some are
quite poor (Altavista used to be great, but has fallen by the
say...) Google.com is the best all around one to try.
Talk to the host, it wouldn't hurt. That's their job, to deliver
the websites to the world.