It is not common, but some hosts may be configured incorrectly with the wrong clock time or may be sending DNS errors that prevent your site from being indexed. You can use a server header checker to ensure that your clock time is not way off (like months or years), that your home page provides a 200 code, and that non-existent pages provide a 404 error code.
You also can use Web Bug or the Firefox Live HTTP Headers extension to check your HTTP headers. See the references section at the end of this chapter for a list of online tools.
Some hosts also improperly configure servers or place spammy subdomains on sites. Be careful if you use a host like iPowerWeb, as some of their clients noticed spammy subdomains that would appear out of nowhere. Search engines may penalize your site for this sort of activity. That is yet another reason to go with a reputable host.