Any chance we can see the site? Matt's completely correct regarding Bing Webmaster Central, I'd start there.

Also:

1. Submit an XML sitemap. Any errors that pop up during the processing of the sitemap will help you diagnose the problem.
2. Check your log files. See if BingBot or MSNBot show up in the logs. If they don't, then your site's not getting crawled.
3. Check robots.txt - any chance the site's outright blocking them?

Generally, I've found that folks coming from internet marketing programs aren't that well prepared. That doesn't mean they wouldn't be good employees! It just means the schools do a lousy job of prepping them.

When I interview them, I use the same kinds of questions I ask anyone: Basic logic stuff, HTML, communications abilities, etc.

But definitely never accept college-level training in 'internet marketing' as a sign someone's better-prepped. And if they're trying to tell you their certificate (whatever that is) is a sign of how competent they are, that's just a sign that they're still pretty naive. Not the end of the world, but they're still beginners.

No way. Google may care about DNS repoints, but that's something else entirely.

Google barely cares about shared IPs and 'bad neighborhoods' at this point - so I doubt the IP address matters. Plus, we have several clients using hardware load balancers that do exactly what you describe, and it doesn't hurt them.

My rule of thumb: If the directory would be a great place to have a presence if Google didn't exist, then do it. Otherwise, I tend to steer clear, post-Penguin.