I worked at a place that had many customers who used a major free email provider that also ran an ad network (but was not Google or Microsoft) that kept deciding that most mail we sent to our customers was spam: receipts, installation instructions, responses from support, and notices that subscriptions were going to re-bill were all blocked.

We'd contact them, they would fix things, and it would work for a while...but invariably it would go back to classifying it all as spam, and we'd get customers calling to complain about not getting instructions or support responses.

Finally, our guy who managed our ad spending called up our rep in ad sales at the email company, and asked in rather forceful terms just why we should continue spending $large_number/month on ads there to acquire new customers, when we were then going to be blocked from emailing those customers?

The ad rep conference called in their head of IT, who conference called in their engineer in charge of spam filtering, and had him right there add us to a whitelist that would prevent anything from us being classified as spam no matter what the rest of their spam system decided. As far as I know we never had another email go into the spam filter.

If we hadn't been spending a large amount on ads with them, I doubt the problem would ever have been resolved.

If you sell a software product to end users, and have non-marketing messages that you need users to see such as responses to support requests or reminders that subscriptions are going to automatically re-bill, I'd recommend including some kind of messaging system specifically for this in the product itself. Still send them as email, but also send them via this in-product channel, or at least send notices that there is a message with links to a way to view it on the web. Email only is simply not reliable enough.