• don't use an IP range classified as "consumer" (known dynamic IP DSL/cable ranges)
• set up SPF
• set up DKIM
• don't send actual spam
…it generally gets through. Mox is so far the easiest solution for SPF/DKIM I've seen, but if you don't mind spending a weekend tinkering, it should be solveable with any email stack.
> In some cases, websites weren't even allowing email registration with a self-hosted email.
I never ran into that issue. Not much you can do there, other than writing the owner angry emails via gmail.