Я не уверен, зачем вам здесь нужны вложенные транзакции. Вам нужна только одна фактическая транзакция:
BEGIN TRAN
DELETE FROM Employee
FROM Employee
INNER JOIN Department ON Employee.DepartmentID = Department.DepartmentID
INNER JOIN Company ON Department.CompanyID = Company.CompanyID
WHERE Company.CompanyID = @CompanyID
DELETE FROM Department
FROM Department
INNER JOIN Company ON Department.CompanyID = Company.CompanyID
WHERE Company.CompanyID = @CompanyID
DELETE FROM Company
WHERE Company.CompanyID = @CompanyID
COMMIT TRAN
Обратите внимание на двойной FROM, это не опечатка, это правильный синтаксис SQL для выполнения JOIN в DELETE.
Каждый оператор является атомарным, либо весь DELETE будет успешным, либо неудачным, что в данном случае не так уж важно, потому что весь пакет будет либо успешным, либо неудачным.
Кстати, я думаю, что ваши отношения были задом наперед. У Департамента не будет идентификатора сотрудника, у сотрудника будет идентификатор отдела.