Get entries with related to selected categories and then group by category
I may not understand fully, but it sounds like you could just loop over the attached Department Categories, then query for Staff related to that category:

{# Load the Departments Categories: #}
{% set departments = entry.allDepartments.all() %}

{% for department in departments %}
  {# Find all the Staff Members associated with the department: #}
  {% set staff = craft.entries({
    section: 'staffMembers',
    relatedTo: department,
    with: ['staffPhoto']
  }).all() %}

  &lt;h1&gt;{{ department.title }}&lt;/h1&gt;
  &lt;ul&gt;
    {# Loop over the Staff Members: #}
    {% for person in staff %}
      &lt;li&gt;{{ person.title }}&lt;/li&gt;
    {% endfor %}
  &lt;/ul&gt;
{% endfor %}



  There is a (very slight) performance penalty for performing queries like this in a loop, but it sounds like each of these focused sub-pages won't have too many Departments listed anyway.