The only thing I can think of without using a custom authentication scheme is to create a new attribute in odsee called something like uidDept, that is meant to contain the user's login ID and Dept concatenated together. Then run a batch script to populate the new attribute and modify your account creation process to populate/modify this field when the account is created and whenever the uid or Dept fields are changed.
Then you could change the login page or the FCC that the login page posts to in order to concatenate the uid and Dept data input by the user into the username field of the FCC, and change your user directory START field to use uidDept instead of uid for disambiguation.
To do a custom auth scheme you would either need to create your own pool of LDAP connections in order to locate the unique user's DN based on a search filter containing both uid and dept during disambiguation, or write the code in C++ and use the Policy Management API's Sm_PolicyApi_LookupDirectoryEntry() method to perform the search with the search filter based on both uid and dept.
Either way, it is not a trivial custom auth scheme to write, although CA Services Global Deployment Software Engineers and possibly some other 3rd party consulting companies have the expertise to do this.