We have never recommended any specific backup method to any provider, as this should be a choice made by the customer, simply if you prefer to have active fulls you would pay more storage, but that's it. In general, we promoted the fact that on cloud connect you can do forever incremental, which is the opposite of the scenario described here.
The only guess I can make is the provider is using a generic deduplication appliance that doesn't like too much synthetic operations, but to be honest pushing users to do active fulls thus consuming more storage space is unfair. Unless the provider is then billing the deduplicated value of the storage consumption, and not the value as seen by Veeam console, but still as we can see here in this thread, there are also issues about bandwidth and backup duration.
EMEA Cloud Architect @ Veeam Software
Veeam VMCE #1