Client barred from using (at)YOURSITE email by webhost, any workaround?

Situation is client is paying $750 a year for domain, hosting, etc. This includes updates to all tax codes and they don't want to change it. All email addresses are (at)InternetProvider instead of (at)Website. I called hosting company to get emails fixed and they said $40 per user per year - not really "barred" but that is robbery. Is there a way to fix the email without going through hosting company? Does anyone have any recommended solutions? I have never run into this issue.

Sincerely,

Use your own mail server, i think thats the best way ? then re-route your a records to use the new mail server instead of the hosts mail server.