Fuzzy Merge - With Two Columns (one with exacth match and other with fuzzy match)

So I understood correctly that you have 100K employees.
But he size of the departments (companies) is 10 times as large as I assumed.

So I tested with 100K employees in 288 departments with on average around 350 emplyees each. I used a normal ditribution for the number of employees per department so that 90% is between 300 and 400 employees.

And I have some good news for you! 

It is even quicker! It is now about 1 minute on my laptop.

So the performace of the FuzzyJoin is not lineair with the number of comparisons it needs to make, but gets relatively more efficient with a bigger dataset.

Here the final query:

let
    Source = #"Employee Data",
    #"Grouped Rows" = Table.Group(Source, {"Department_Id"}, {{"Employees", each _, type table [Department_Id=nullable number, Employee_Id=nullable number, Employee_Name=nullable text]}}),
    #"Added Custom" = Table.AddColumn(#"Grouped Rows", "Custom", each // the following executes for each row.
            let // to break up a otherwise complex fromula (does not impact perfomance) 
                // load this department employees in memory
                employee_buffer = [Employees], // Table.Buffer([Employees]),  // tried buffering, but did not make any difference
                // Create a table with matching employee names
                Matched = Table.FuzzyNestedJoin(employee_buffer, {"Employee_Name"}, employee_buffer, {"Employee_Name"}, "Fuzzy Matched Employees", JoinKind.LeftOuter, [IgnoreCase=true, IgnoreSpace=false, Threshold=0.9, NumberOfMatches=1]),
                // Add the Employee Id's and Employee Names of the matches
                expanded = Table.ExpandTableColumn(Matched, "Fuzzy Matched Employees", {"Department_Id", "Employee_Id", "Employee_Name"}, {"Fuzzy Matched Employees.Department_Id", "Fuzzy Matched Employees.Employee_Id", "Fuzzy Matched Employees.Employee_Name"})
            in
                // Select only the employees not matching themselves and return the outcome
                Table.SelectRows(expanded, each [Fuzzy Matched Employees.Employee_Id] <> [Employee_Id])
        ),
    // Get the Employee_id and Employee Names into the departments table
    #"Expanded Custom" = Table.ExpandTableColumn(#"Added Custom", "Custom", {"Employee_Id", "Employee_Name", "Fuzzy Matched Employees.Employee_Id", "Fuzzy Matched Employees.Employee_Name"}, {"Employee_Id", "Employee_Name", "Fuzzy Matched Employees.Employee_Id", "Fuzzy Matched Employees.Employee_Name"}),
    #"Filtered Rows" = Table.SelectRows(#"Expanded Custom", each [Employee_Id] <> null)
in
    #"Filtered Rows"

Please mark this as solution if you can use it (even if it only helps you to decide NOT to use PowerQuery for the fuzzy matching...)