In my organisation we are planning to do something similar, but with guest users being able to trigger flows.
The way this has been explained to me by our MS solutions provider is that flows should be "configured" to run using a service account within the tenant. External users wont directly trigger the flows but their actions will, such as 'When an item is created’, ‘When an item is created or modified’ etc. This will only work if we are not using any Premium Connectors - so we wont need additional licenses. However, if you are using any Premium Connectors you will need at minimum a Power Automate Per User license to be pinned to the service account executing the flows.
This sounds similar to the advice from your colleague.
A colleague suggested we watch (I haven't watched it yet):
Power Apps & Power Automate Licensing Overview:
https://www.youtube.com/watch?v=E7T9xipjXfE
"Priya Kodukula (Microsoft) and Reza discuss the PowerApps and Power Automate licensing options & answer your licensing questions."
Ellis
