SenderID for shared hosting

I have a client who is using an off the shelf hosting package from one of the large hosting companies. Their DNS is managed by the hosting company. To date they have been sending out newsletters using a run of the mill email program (Outlook). I have convinced them to use CM and am in the process of setting it up. This is where the problem comes in. I need to ensure their newsletters gets though to their clients as they have been from their standard mail program. ie from their DNS. I am worried that a mail coming from DNS: will end up in their clients spam filter.
I have spoken to their host company to try and get Sender ID and DNS keys setup but have been told this is only available to dedicated hosting and DNS management.
Is this correct?
If this is the case it there a way I can work around this? If so how?
I realize there are other factors at work regarding spam and am not saying the is the problem but most of the people who work with them have my clients email address in their sender list and therefore on their white list.
Will having the clients email as the send and return address ensure it gets through the spam filter or does most of the filtering hang off the DNS?
All help welcome

200,000 companies around the world can't be wrong.

From Australia to Zimbabwe, and everywhere in between, companies count on 
Campaign Monitor for email campaigns that drive real business results.

Get started for free