¿ Making Employee ID unique in a big company ?

The Employee ID field on employee records must be unique. If you have a Mark Smith and try to create another Mark Smith, you get an error:

There is already an employee with external access to this account using that entity name. All employees with external access must have a unique entity name for login purposes. Go back, change the entity name and resubmit.

This happens even if Mark Smith doesn't (and never did) have login access.

My company is only about 750 people, but we already have some folks with the same name. We're in the midst of an effort to begin using an employee's numeric id to integrate our systems. I already have that id pointing to External ID, and now I'm considering appending it to the Employee ID field. For the first Mark Smith, his Employee ID may now be "Mark Smith 12345", while the 2nd Mark Smith would be "Mark Smith 67890"