Microsoft (Outlook, Hotmail) won’t accept your email without paying them, or forwarding through someone who does
That's absolutely not true. They sometimes bork some messages and signatures internally, but aside from that, delivery to MS stuff (and that includes a lot of business behind their "outlook protection" service) has been fine for years.
And, contrary to old beliefs, it has been mostly fine all around. Just properly setup DKIM, your DMARC and SPF records, and don't actually send spam. The worst that could happen is if you're trying to send through some residential IP, as large blocks can occasionally get blocked. But a cheap hosting anywhere (even in a spamfarm-ridden provider) is very likely to work fine.