It would of be much easier if you could tell us the domain you are speaking about.

Apart that, is the site build in a new domain, or it is an old domain that you have recently purchased by someone, if it is old, you might want to have a look at the history of the domain.

Is your domain also having difficulties to get indexed on all search engine's or you have difficulties with one search engine in particular?

Sometimes, especially when the domain is old and has a history (most probably bad one) the domain has difficulties to get indexed, has happened to me before for a clients domain, but now he has already got indexed.