There are three different roles involved: end users, the company, and the provider. There already is some legal relationship between the end users and the company.
Your question seems to boil down to: can the company create a legal relationship between the provider and the end users?
- The company cannot enter any agreements on behalf of the end users, unless the end users have provided the necessary rights.
- It may be possible for the company to transfer its end user relationship to the provider, with the new provider remaining bound by existing agreements.
- The company may be able to unilaterally change its terms of service offered to the end users, but not all such changes are valid.
But in practice, nothing like this will be happening: there won't be any legal relationship between the end users and the provider, only between the company and the provider. The company might then appear as a reseller. The company can only engage that provider if their agreement with the end user allows this.
A practical example: The company provides an email service. It wants to stop self-hosting the email and outsource the service to some provider.
Scenario A: The current terms of service state that the emails will be stored on servers in Switzerland, but the new provider would be in Australia. Engaging the provider would violate the terms of service in the current form, but the ToS can likely be changed with some advance notice that allows users to delete their account if they don't agree with the changes.
Scenario B: The company's current agreement with end users makes certain privacy guarantees. The company ensures that these guarantees hold even when outsourcing to that provider. For example, they might have a contract with the provider that controls how the provider can process the end user data.
By the way, that scenario B would be a GDPR-compliant approach: the company acts as a data controller, and can take on data processors if they sign a data processing agreement that binds the processor to only use that end user data as explicitly instructed by the controller. That way, any use of the data remains under the authority of the controller. Things only get problematic when the provider wants to use the data for their own purposes.