Based on what you've described, I agree that the 409 Conflict response on the /api/v2/users/{userId}/presences/purecloud endpoint seems to be the key point to investigate. The contentsquare and gcba errors don't appear to explain why the presence update itself is being rejected, especially if they have always been present in your environment.
Since you already have a Customer Care case open, I'd recommend requesting an escalation to the team responsible for Presence so they can troubleshoot the issue together with you. The exact reason for the conflict should be visible on the backend.
As an additional check, I'd verify whether the affected users have anything in common, such as the same integration controlling presence (if any), the same division, role, or routing configuration, and whether the issue affects only existing users or can also be reproduced with a newly created test user.
------------------------------
Raphael Poliesi
------------------------------