То, что вы хотите, требует двух запросов.
Запрос1:
SELECT DISTINCT PatientID, DepartmentID FROM PatientTestIDs;
Query2:
SELECT Count(*) AS PatientsPerDept, DepartmentID FROM Query1 GROUP BY DepartmentID;
Вложено все в одно:
SELECT Count(*) AS PatientsPerDept, DepartmentID FROM (SELECT DISTINCT PatientID, DepartmentID FROM PatientTestIDs) AS Query1 GROUP BY DepartmentID;
Вы можете включить таблицу Departments в запрос 2 (или вложенную версию), чтобы добавить описательные поля, но вам придется включить эти дополнительные поля в GROUP BY.