For example if I have 2 different auth0 accounts with different tenants for 2 separate applications ( to separate user data) but they will be using a shared 3rd party service that assumes the user_id are unique. Would this be possible?
For connections where the user identifier is generated internally the guarantee is that the identifier will be unique across the same tenant account. This means that there may exist user accounts with the same user identifier if you look in more than one tenant account. A good example will be a social connection user account, for example from Google, that will have the same user identifier either in tenant A or in tenant B because in this case the user identifier is derived from the Google account which remains stable no matter the Auth0 tenant.
The above implies that your scenario may or may not be feasible; in some situations if for example you only used custom database connections then you could ensure the globally unique user identifier. However, the recommended approach would be to keep it simple and obvious and use a combination of tenant account identifier and user account identifier as the unique key for the third-party service.