After considerable research, today I answer myself: YES, it IS a hosting provider issue. Here are the reasons:
Today, SPF alone is not enough anymore to validate a sender for any serious email provider. Because of email-deliverability, more and more businesses rely on third-parties especially for newsletters, but not only: my office environment might rely on a cloud provider to enhance workflows, including emails, which will only rarely correspond with the domain hosting provider.
Consider that I might send my newsletters through someprovider.com. So I need to insert someproviders SPF space into my SPF record. But someprovider might be hosted by somecloudservice and have shifting IP addresses. In that case, someproviders SPF record might actually include the full address space of somecloudservice.
This means that anybody else hosted not only on someprovider, but even on somecloudservice could spoof my emails, and SPF validation would still work!
That is one reason why gmail and other services will clearly indicate you that the email you received was sent through a third party (See google support documentation).
For the same reason, Outlook / office 365 could flag such email as SPOOF (see here: microsoft office 365 documentation).
Only a valid DKIM signature can certify the actual sender of an email. That is why DKIM was created in the first place (Details: Wikipedia article - DKIM.org official website).
Since spoofing and phishing is an ever-growing issue, anybody should have the instruments to know who was the sender of a given email.
This is why I strongly propose that any serious hosting provider should not only implement DKIM, but possibly activate it by default.
Also, I am quite sure that big email providers like the ones mentioned above, will soon start to penalize any emails which are not DKIM signed, especially since it has become an official internet standard already in 2011 (see Wikipedia article above). Spam & spoof are still a growing problem, and there will be a growing tendency to filter out any email which is not clearly legitimated.
So, we have changed our email provider, as without DKIM we have a smaller and smaller chance of our emails (not only newsletters, but daily business emails) reaching the inbox of the intended recipent.
Six months after having transitioned to our new email provider, I can confirm that the consequent implementation and use of DKIM has resolved ALL of our previous delivery issues.