LowEndTalk.com will help you find a super cheap VPS.
However I would advise using dedicated hardware for the server instead for improved privacy. There are two possible routes:
1) Rent a cheap dedicated server such as the Kimsufi line by OVH or the Personal line by Online.net. These cost below 10€ a month.
2) Run the email service on your box at home and use the cheapest VPS you can find just to tunnel a non-dialup IP address to that box using OpenVPN. The cheap VPS usually costs less than $10 per year.
I would prefer to go with the known name and well-established company, instead of LET, for email.
For example, Vultr offers $2.5/mo servers from two locations and they are proven, to be trusted hosting company. In case your IP has a bad reputation (you can test it right after spinning an Instance), you can just shut the server down and create a new one with fresh IP.
Problem with both Kimsufi and Online.net is that if you will get a bad reputation IP it is quite hard to get a new one. I have dealt with OVH and a blacklisted IP I have got on a new server and they were expecting me to contact blacklist providers and request whitelisting, which took time and resources.
When renting a dedicated box, a VNC-like interface is required to enter disk encryption password, which could be intercepted by the host. Moreover, this has to be done on each restart. I look at dedicated box more as an upgrade from VPS.
For privacy, I think user encrypted email messages provide the best option.
At home self-hosting through VPN is a good idea. It would involve maintaining hardware, which I traded for low cost VPS. With a replica backup MX, I am not married to any hosting provider, and can hop without downtime.
" a VNC-like interface is required to enter disk encryption password, which could be intercepted by the host. "
There's a rule in security that anyone in physical possession of your device should be assumed to have access to it. The host has the server whether physical or virtual. You're not safe from them. Trusting them is the tradeoff made for the cheap, hosted server.
" I look at dedicated box more as an upgrade from VPS."
Multiple VPS's share a physical box. A malicious VPS can look for secrets in another VPS using side channels. This isn't possible on bare metal: they have to compromise an app or get a shell first. The next concern would be endpoint security. OpenBSD covers that well. Then, there's host or peripheral firmware which is almost always a risk if a 3rd party is hosting things. Your attack surface does go down, though, when you're not sharing a box with an attacker. There's also the performance benefits.
Privacy from host is not possible, and you make a very good point about hardware access.
Virtual machine are secured by the shared host. I don't really expect top security from this end. A replica backup MX enables me to safely change hosts, if they behave badly.
OpenBSD defaults are what I base my endpoint security on, and keeping this updated is super easy.
"Virtual machine are secured by the shared host. "
Virtual machines are not secure in mainstream implementations. The tech they use has had a lot of vulnerabilities in the past. Google and Amazon even have their own custom versions for improving security. There's also no covert/side channel analysis done on those to even know what information leaks will be found in the future. Finally, hardware-level attacks are possible if you have malicious code running that bypass VM protection. Most popular recently is Meltdown/Spectre.
There's only been a few VMM's designed for security (two examples below). Most of them probably cost five to six digits to license. The FOSS ones are alpha or beta quality without the tools a big host would want for management. The VMM's focused on rapid development of features in unsafe languages don't look anything like the ones that passed pentesting. They also have highest marketshare due to those features. So, your host serving cheap VPS's is almost certainly not using a secure VMM: they're saving money using an insecure one on insecure hardware that they're patching as vulnerabilities are publicized. Like almost everyone does with their OS's for their beneficial features. ;)
There's no need for a visual desktop just to enter the passphrase. You can also do it by logging into a minimal setup that is inside the initrd via SSH (dropbear).
It is a standard debian feature.
Kimsufi IPs often end up on spam blacklists. Is DKIM etc. enough to circumvent that or wouldn't your connection with other mail servers not even come that far?
It depends on the email service provider. In general, you're in for a bad time. You can make it work, but you're always going to be fighting black lists and the occasional ESP who blocks your entire provider.
However I would advise using dedicated hardware for the server instead for improved privacy. There are two possible routes:
1) Rent a cheap dedicated server such as the Kimsufi line by OVH or the Personal line by Online.net. These cost below 10€ a month.
2) Run the email service on your box at home and use the cheapest VPS you can find just to tunnel a non-dialup IP address to that box using OpenVPN. The cheap VPS usually costs less than $10 per year.