It really depends on your companies data integrity needs and goals. Microsoft doesn't really back up your data and when you know how what they do works, you can see the potential holes in that strategy. If those potential holes aren't an issue, then a 3rd party backup is probably not worth it. That's a business decision, not an IT one.
From a product standpoint, we use Veeam for Office 365. Veeam is a world class backup and recovery product and their support and development cycles support that.
There are 3rd party services that can host the storage or you can do it all on-premises if you have the resources. Cost is around $1/user and total storage is built up based on total users. So you can't just get one account and backup 40tb of data.
They offer a free 10 user, 1TB community version as well, if you want to try it out.
