[SalesForce] Queueable Apex in a Before Trigger

I am attempting to create logic that, on Contact record insert or update, will compare the Phone value of the record to another reference object and conditionally populate a checkbox as a result of the comparison.

The first iteration passed unit and functional testing, but was found to cause Apex CPU timeouts under high volume. Therefore, I made the class queueable.

After converting the class, I am now in a situation where testing in the UI works as desired/expected but each unit test returns this error: System.DmlException: Update failed. First exception on row 0; first error: MISSING_ARGUMENT, Id not specified in an update call: [] here Class.CellPhoneIndentifier.execute: line 91, column 1

There isn't too much out there on same record update in a before trigger insert/update using queueable Apex, but this post seems to indicate this whole approach should not work and that I should be working on Ids instead of SObjects as in a future method.

So I'm confused as to why the UI works, but the tests don't and also why current logic appears to work at all when it apparently shouldn't.

     public class CellPhoneIndentifier implements Queueable  {

    --trimmed--

        public CellPhoneIndentifier (List<Contact> contactList, Map<Id, Contact> oldMap) {
            this.contactList = contactList;
            this.oldMap = oldMap;
        }


        public void execute (QueueableContext context) {    

    --trimmed--

            //Loop through contacts to check and see if they are in the mobile contact list
            for (Contact cont : contactsToCheck) {
                if(mobileContact.contains(cont) && cont.Preferred_Phone_is_Mobile__c == false) {
                    cont.Preferred_Phone_is_Mobile__c = true;
                    contactsToUpdate.add(cont);
                } else if (!mobileContact.contains(cont) && cont.Preferred_Phone_is_Mobile__c == true) {
                    cont.Preferred_Phone_is_Mobile__c = false;
                    contactsToUpdate.add(cont);
                }
            }

            update contactsToUpdate;
        }

--trimmed--

@isTest
public class CellPhoneIdentifierTest {

//Get Household recordtype ids
static Id contactHouseholdTypeId = Schema.SObjectType.Contact.getRecordTypeInfosByName().get('Household').getRecordTypeId();

@TestSetup
static void setup() {

    Cellphone_Reference__c wirelessId = new Cellphone_Reference__c(Wireless_Block_Identifier__c = '9206430');
    insert wirelessId;

    List<Contact> testContacts = new List<Contact>();

    Contact nonCellContact = new Contact(LastName = 'nonCellContact',
                                    HomePhone = '920-247-2477',
                                    rC_Bios__Preferred_Phone__c = 'Home',
                                    RecordTypeId = contactHouseholdTypeId);

    testContacts.add(nonCellContact);

    Contact cellContact = new Contact(LastName = 'cellContact',
                            HomePhone = '920-643-0489',
                            rC_Bios__Preferred_Phone__c = 'Home',
                            RecordTypeId = contactHouseholdTypeId);

    testContacts.add(cellContact);

    Contact shortContact = new Contact(LastName = 'shortContact',
                                        HomePhone = '920-6',
                                        rC_Bios__Preferred_Phone__c = 'Home',
                                        RecordTypeId = contactHouseholdTypeId);

    testContacts.add(shortContact);

    Contact nophoneContact = new Contact(LastName = 'nophoneContact',
                                        RecordTypeId = contactHouseholdTypeId);

    testContacts.add(nophoneContact);

    insert testContacts;
}

//Tests a Cell contact being inserted
@isTest
static void insertCell() {
    Contact contactInsert = new Contact(LastName = 'TestContact',
                                    HomePhone = '920-643-0489',
                                    rC_Bios__Preferred_Phone__c = 'Home',
                                    RecordTypeId = contactHouseholdTypeId);

    Test.startTest();

    insert contactInsert;

    Test.stopTest();

    contactInsert = [SELECT Id, Phone, Preferred_Phone_is_Mobile__c FROM Contact WHERE LastName = 'TestContact'];

    System.assertEquals(true,contactInsert.Preferred_Phone_is_Mobile__c);
}
--trimmed--