I wouldn't go with free. If you do get smtp access at a free mail host, every spammer on the planet will be using it as well and you will have the same problem.
I use this. Takes a little digging, but you can configure a separate outgoing address for your site to use via smtp. Actually there is alot of power under the hood there. The drawback is you need to configure entire domains mail there, and then pay per user. That's not per mailbox tho. For example, you would pay for alex, betty, and charles to have login credentials, from there each can have there own inbox and folders, then you can add a separate shared mailbox that all 3 have access to, configure an outbound email for your site to use via smtp, configure an alias for president that goes to alex and a few more aliases if you need them....and so on, you can get as complex as your needs are. All that you still just pay for 3 users. If you only have one user that's fine to... you can sill configure more than one inbound/outbound address.
All shared hosts have mail issues, its a hot bed for outbound spam. Pay for shared hosting and use it for webhosting. Pay a business class email provider for business class email. There is a difference.
If share hosting meets your web hosting needs, and you don't need many email users, then paying for separate business class email plus shared hosting is still going to run you less per month than a VPS.