In the same boat and now actively considering just self-hosting as these threads will so often advocate for. What a pain.
Being bounced as spam not an issue for me.
YMMV depending on who had your IP address previously. If you get a bad (previously blacklisted) IP, then you can always spin up a new VM.
Some of the really low-end VPS providers are so relaxed they get their AS number blacklisted in uceprotect.