This can occur when all the following are true:
Implementation of VPP App as required or available.
User-based licensing is used to deploy the VPP App.
After the RegisterVPPUserRequest between Intune and Apple's VPP service is completed, the Intune user is linked to an AppleID via a VPP invite and the user accepts the terms and conditions.
Intune generates a clientUserIdStr which is directly tied to the Intune user for the life of the Intune user account solely based on the AppleID that accept the program invite. Per Apple specification and terms and conditions presented to the user accepting the invite, the MDM (Intune) will never have the knowledge of the users AppleID, thus if the Intune user on any iOS device uses a different AppleID, because the only Intune association is the clientUserIdStr, VPP license assignment will not be associated with different AppleID.
An Intune user will be assigned a clientUserIdStr that is directly linked to his or her Intune account for the duration of the account, solely by virtue of the Apple ID that accepts the program invitation. A MDM system (Intune) will not know the AppleID used by the user accepting an invitation. Thus, if the Intune user on any iOS device uses a different AppleID, VPP license assignment will not be associated with the host AppleID.
Note: This may also occur because of deletion of the Apple ID from Apple Business Manager.
If the VPP license is already associated with the AppleID, or the user has another device enrolled with Device Enrollment, the license will associate to the AppleID successfully. However, if the only iOS device the user has enrolled is User Enrolled, the VPP license assignment will fail and install will fail with Can't Find VPP License For App
Changing the License Type and enrolling the device as Device Enrollment fixes the issue
Applications were synchronized and appear in Intune, where groups of users can assign them.
The Application that was marked "Required" was relatively easy to fix.
Click on “User” of License Type of Assigned group
Change the License type
The Application that was marked "Available" was not straightforward since Licensing type was greyed out.
The assignment must then be removed and started again.
For BYOD users having this issue, after enrolling your device as device enrollment with device licensing, please re-enroll your device in User enrollment with user licensing.
Note: In case any new VPP application will be assigned to user, user will face the same issue and we have o perform all the steps again including device enrollment.