So a colleague of mine figured it out and helped me, so I'm posting this for anyone looking for this.
- Go to https://myaccount.microsoft.com/organizations. You'll be logged in for you main account.
- Top right, click your account and choose 'Switch organisation' (instructions continue after image)
- Choose the organisation of which you need a QR code to verify (instructions continue after image)
- Approve the sign-in on your old device
- In the left menu, choose 'Security info'
- Don't be fooled by the logo in the top screen! It will show the company logo of your main account, instead of the company logo of your guest account. So you might think you're back where you started, but you're not!
- You'll probably see your old phone and not your new as a registered device. Click 'Add sign-in method' and follow the instructions! (instructions continue after image)
- Repeat for any other companies you have a guest account for! ;)
I hope this helps anyone in the future, looking for this answer just as I did!