@Nathaniel Thomas, Thanks for posting in Q&A. From your description, I know the app can be installed and uninstalled successfully. But the shortcut is not working. And from the error message, it seems the shortcut open and want to access some resource outside. But the network is blocked. For such issue, I think you can capture network log to find which resource is blocked. You can contact networks support engineer to look into the issue.
In Intune, there are app types like win 32, store app and etc to deploy app. But for app-v, I don't find other method to deploy the app.
https://learn.microsoft.com/en-us/mem/intune/apps/apps-add
Hope the above information can help.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.