How about using a non-changing LDAP attribute as the username? Employee ID and email address (for example) are unlikely to be reused for different employees, since reusing them would create problems in other business processes/applications/systems.
The issue seems to be with business processes that allow reusing of "identifying" attributes rather than with Moodle, and it's likely that the issue being seen by OP is affecting other systems as well.