I know there are two ways to use SendGrid (and probably Mandrill too). You can either let it tack on its own domain as the effective "from" address for security purposes, and not worry about doing SPF, DKIM, etc. for your own domain. That's what I do and that's probably what your client was doing. It's the easiest approach, and I'd like to add that I've never encountered deliverability problems with it, after having used it for Todd, RLE Link and all room scheduling mail.
The other thing you can do is "whitelabeling". That's probably what @samrueby is doing. In that case, you set up your own domain with all of the security stuff and then you tell SendGrid or Mandrill not to stick their own domain into the messages. In that case, there should be no way for destination mail servers to know that SendGrid or Mandrill is involved, except maybe if they keep a list of IP addresses used by those companies and block everything coming from them.
Either way, this client's experience does not sound typical.