Host for Opt in list user

[CyberGarage]

I have a client that I am looking for a new host for. They have an opt in list that they send weekly emails to using their own server. The issue they have is one of their subscribers had reported an email from back in May as Spam and the current host suspended the account. They were told to suspend all emails or they would be permanently shut down. The problem is they are completely CanSpam compliant and can not afford to be shut down because some subscriber decides they no longer want to receive the emails but doesn't want to bother to unsubscribe. I am looking for a host that would give them the opportunity to provide proof the user opted in before any suspension occurred? I know that Spam is a huge problem for hosting providers and anymore, most have a guilty until proven innocent policy. Does anyone have a recommendation of a host that would fit the needs of my client. I could set them up on a Spam friendly host but they cost way to much let alone neither my client or I want any association to them.

Thanks for your time.
Mark