I'm skeptical of this unnamed company's actual abilities. In the initial email how are they able to identify anything about your visitors before you've installed the tracking code? Since they apparently can see search terms used to reach your site the only thing I can think of is their code is running on some site that links to you (perhaps an off-brand search engine?) and they're tracking outbound clicks. Or it's fake.

It's pretty easy to guess company name from IP address, especially if you don't care about accuracy. You can kinda sorta do this in Google Analytics under Audience > Technology > Network. That seems to be roughly what they're doing in the screenshots posted. IMHO, this is not the most serious privacy issue on the web.

I would be very curious to hear exactly what percentage of visitors it is able to supply Name and Email for (and how many of those fields look bogus). This sort of individual-level tracking across sites is obviously possible, but I don't think it's common. Google/DoubleClick do not, as far as I know, do any sort of tracking at the level of an individual's name or email address (And why would they? It's asking for regulatory problems and it doesn't really help them much -- they target ads to groups of similar people based on demographics, not to particular named individuals.)