How to store external IDs from different sources?
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.