The error message typically means that the user with the ID does not exist or has been deleted in the tenant.
When your application receives a change notification, it indicates that a change has occurred. However, it does not guarantee that the changed resource will be available when you try to access it. For instance, if a user is deleted immediately after being updated, your application may receive a change notification indicating the user was updated, but when your application tries to access the user, it gets a 404 Not Found error because the user has already been deleted.
Does this only happen immediately or after a delay? Does it happen for all users or recently created users?
My suggestion is to try the API call few times with a slight delay to handle scenarios like this.