Thanks for your reply.

To begin with, here are the other triggers involved:

trigger AgencyTrigger4 on Account (after update) {

//Create an empty set of Id's
Set<Id> accountSet = new Set<Id>();

//Fill that set with all Accounts where the Record Type changes away from Agency
for (Integer i = 0; i < Trigger.new.size(); i++){
    if (Trigger.new[i].RecordTypeId != '01220000000Dqq6' && Trigger.old[i].RecordTypeId == '01220000000Dqq6') {
        accountSet.add( Trigger.new[i].Id);
    }
}

//Create a list of Accounts where the Agency is in the above set
Account[] updateAccounts = [SELECT b.Id, b.Agency_Lookup__c FROM Account b WHERE b.Agency_Lookup__c IN :accountSet];


for ( Account accts :updateAccounts ) {
        accts.Agency_Lookup__c = NULL;
}

//Run the update
update updateAccounts;

}

 Here:

trigger ContactTrigger3 on Contact (after insert, after update) {

Map<Id, Contact> contactsMap = new Map<Id, Contact>();

for (Integer i = 0; i < Trigger.new.size(); i++){
    if (Trigger.isInsert) {
    contactsMap.put( Trigger.new[i].Id, Trigger.new[i]);
    }
    else
    if (Trigger.new[i].Accountid != Trigger.old[i].Accountid)  {
        contactsMap.put( Trigger.new[i].Id, Trigger.new[i]);
    }
}

RecordUpdate.updateContacts(contactsMap.keyset());

//for (Contact[] updateContacts : 
//    [SELECT c.id, c.Parent_Company__c, c.Accountid, c.Account.Department__c, c.Account.Parent_Company__r.id
//    FROM Contact c
//    WHERE c.id IN :contactsMap.keyset()]){
    
//        for (Contact child :updateContacts) {
//            if (child.Account.Department__c == TRUE) {
//                child.Parent_Company__c = child.Account.Parent_Company__r.id;
//            }
//            else
//                child.Parent_Company__c = child.Accountid;
//        }
        
//    update updateContacts;
    
//}
}

 And here:

trigger OpporunityTrigger6 on Opportunity (after insert, after update) {

Map<Id, Opportunity> dealMap = new Map<Id, Opportunity>();

for (Integer i = 0; i < Trigger.new.size(); i++){
    if (Trigger.isInsert) {
    dealMap.put( Trigger.new[i].Id, Trigger.new[i]);
    }
    if (Trigger.isUpdate) {
        if (Trigger.new[i].Accountid != Trigger.old[i].Accountid)  {
            dealMap.put( Trigger.new[i].Id, Trigger.new[i]);
        }
        else
        if (Trigger.new[i].Agency_Client__c != Trigger.old[i].Agency_Client__c)  {
            dealMap.put( Trigger.new[i].Id, Trigger.new[i]);
        }
    }
}

RecordUpdate.updateDeals(dealMap.keyset());

//Opportunity[] dealstoUpdate =
//[SELECT c.id, c.Parent_Company__c, c.Accountid, c.Account.Department__c, c.Account.RecordTypeId, c.Account.Parent_Company__c, 
//c.Agency_Client__c, c.Agency_Client__r.Parent_Company__c, c.Agency_Client__r.Department__c
//FROM Opportunity c WHERE c.id IN :dealMap.keyset()];

  
//for (Opportunity child :dealstoUpdate) {
//    if (child.Account.Department__c == TRUE) {
//        child.Parent_Company__c = child.Account.Parent_Company__c;
//    }
//    else if (child.Account.RecordTypeId == '01220000000Dqq6'){
//        if (child.Agency_Client__r.Department__c == TRUE){
//            child.Parent_Company__c = child.Agency_Client__r.Parent_Company__c;
//        }
//        else
//            child.Parent_Company__c = child.Agency_Client__c;
//    }
//    else
//        child.Parent_Company__c = child.AccountId;
//}
        
//update dealstoUpdate;
    
}

 And here is the test class I am running:

@isTest
private class TestDepartmentConvert2 {

static TestMethod void TestCompanyChanges (){

//Create records
Account department1= new Account (Name='dept1');
insert department1;

Contact contact1 = new Contact (LastName='contact1', AccountId=department1.Id, RecordTypeId='01220000000Dqq9');

Opportunity deal1 = new Opportunity (Name='deal1', AccountId=department1.Id, Stagename='proposal', CloseDate=date.today());

Sales_Invoices__c invoice1 = new Sales_Invoices__c (Company__c=department1.Id, Parent_Company__c=department1.Id, SUN_Account_No__c='D');

Account parent1 = new Account (Name='parent1');

Account parent2 = new Account (Name='parent2');

Account agency1 = new Account(Name='Agency1', RecordTypeId='01220000000Dqq6');

Test.startTest();
insert contact1;
insert deal1;
insert invoice1;
insert parent1;
insert parent2;
insert agency1;
Test.stopTest();



//Update department
department1.Department__c=TRUE;
department1.Parent_Company__c=parent1.Id;
department1.RecordTypeId='012R00000004l05';
update department1;


//Update department with new parent
department1.Parent_Company__c=parent2.Id;
update department1;


//Update Department to non-department
department1.Department__c=FALSE;
department1.Parent_Company__c=NULL;
department1.RecordTypeId='01220000000Dqq8';
update department1;


//Update deal to new Company
deal1.AccountId=parent2.Id;
update deal1;


//Update parent2 to be rep by agency
parent2.Agency_lookup__c=agency1.Id;
update parent2;

//Update Deal to be for agency
deal1.AccountId=agency1.Id;
deal1.Agency_Client__c=parent2.Id;
update deal1;


//Update parent2 to Department
parent2.Department__c=TRUE;
parent2.Parent_Company__c=parent1.ID;
parent2.RecordTypeId='012R00000004l05';
update parent2;


//Update parent1 to be with agency
parent1.Agency_lookup__c=agency1.Id;
update parent1;


//Update Deal to different agency client
deal1.Agency_Client__c=parent1.Id;
update deal1;


//Update Contact to new Company
contact1.AccountId=parent2.Id;
update contact1;

//Update Agency to non-Agency
agency1.RecordTypeId='01220000000Dqq8';
update agency1;


//Delete Records
delete department1;

}
}

I will do some further testing today and see how it goes.

Thanks again.