So, on all of our sites that are not search facing we've applied a robots.txt file (per How to exclude a website from real-time Google search results ?, or any other similar question).
However, if search terms are specific enough, the domain itself can be found via results. An example of this can be found here. As you can see from the link, the domain itself can be found (content is not cached, but domain is listed). Additionally, performing a search with site:hyundaidigitalmarketing.com should 3 results. Checking backlinks provides a few as well, but I obviously cannot prevent them (linking is allowed in context) or control how these are handled (can't tell the host to add nofollow, noindex).
Now, I know this is a severe edge case, however my companies clients are doing just this. In fact, our domains are pretty good, so even seemingly arbitrary searches are turning up relevant results. Now, I have to write up a report on how/why this is happening.
So, I turn to the wonderful Stack Exchange network to help me either understand what I am missing or understand what is happening. Links to industry articles are extremely helpful but, anything you can give is obviously greatful. I do intend to offer bounties the best I can to make this an answer to turn to in the future.
Edit: I've opened a bounty on this question in hopes of getting some more responses on it. I've also provided the results of my own research below.