The domain is, or can be, a separate thing from the hosting.Gotcha, thanks do you have a VPS you recommend or place to start on this?
What I did was to purchase the domain somewhere with a proper DNS control panel (personally I use Cloudflare, which is very cheap -- US $8.57/year for a .com), and then create DNS records to point the mail extensions to your hosting, which can be managed by third parties or on a VPS. You can point the mail extensions of the DNS to a VPS, and the web to others. It's quite flexible.
All my email hostings are managed by third parties on which I trust, so I will leave the VPS part of the set up for others to recommend.