I found the solution to my problem. I needed to add the agents IP-address in the corresponding Storage Accounts Firewall exceptions (where the Workspace/model was stored). For others facing the same problem, this is valid for "Azure Hosted Agents" as well.
Added a task in the corresponding agent that ECHO:ed its own IP-address, which I then added to the firewall exceptions. Location of Firewall settings