What is the best practice to handle multiple external IDs on object? F.e if accounts are coming from multiple systems, should each external ID be kept in its own field?
It is better to design data storages in a way that you can use single External Id to lookup same record in multiple systems with having one Data Storage as source of truth
If you have System A,B,C separated are interacting with each other interacting only with Salesforce you can use single external id.
If you have complex infrastructure where Systems A,B,C interacting with each other and Salesforce and you can't identify source of Master Data you will need multiple External Id fields: Approach here I would take is to reorganize system to have or single source of truth DB or some corporate API that manages interaction within these systems
You can combine your external Id with sales force ORG ID. So that external ID will never repeat throughout sales force platform. This will work if external system also an salesforce integrated.
Incase external system not an salesforce, you need define unique system number for your external system, Combine with external Id.
This will maintain an uniqueness throughout your flow.