How to store external IDs from different sources? I have a table of customers with a PK that we can use as an identifier for our internal system. These customers may belong to different companies, each of which may have an external ID in some arbitrary structure to identify the customer. Furthermore, customers and companies have a many to many relationship.

My dilemma is whether I should store the external ID in the linking table itself or via some external table (because the external IDs may be of arbitrary form). We need to be able to find customers for a particular company via internal or external ID.
The fact that the ExternalID is in an arbitrary format should not impact the design of the schema. As it's a many to many relationship, you can use the following:

Customer
- ID
- Name
- etc...

CustomerCompany
- CustomerID (PK, FK to Customer)
- ExternalID 
- CompanyID (PK, FK to Company) 

Company
- ID
- Name
- etc...


Depending on the business logic, it may also make sense to include ExternalID in the primary key for the CustomerCompany table.