Issue with "Send email from shared mailbox"

We have recently had issue that new flows using the Outlook step "Send from shared email box" are failing. If I create an manually triggered flow that sends an email from the shared box and I run it, it works.

if I then share that flow with another user and they run it using my credentials for the outlook step, it fails with this error