Problem/Context:

• Approval process exists identically on orgs DEV and INT.
• Test passes on DEV, but fails on deployment validation to INT
• Test failure on deployment validation is that the SOQL query returns 0 rows.

Attempted Fixes:

• enable SeeAllData
• Move around the Test.startTest and Test.stopTest methods
• Use StepsAndWorkItems related list on ProcessInstance
• Remove specific approval process Id on test
• Move data creation out of @TestSetup method

Test Code:
    @TestSetup
    static void before() {
        List<User> userList = createNewUserList(NUM_USERS, false);
        insert new List<User>{userList[PENDING_APPROVER]};
        userList[PENDING_SUBMITTER].CustomObj_Approver__c = userList[PENDING_APPROVER].Id;
        insert new List<User>{userList[PENDING_SUBMITTER]};
        CustomObject__c pendingObj = new CustomObject__c(
            Name = PENDING_OBJ_NAME,
            OwnerId = userList[PENDING_SUBMITTER].Id
        );
        
        insert new List<CustomObject__c>{pendingObj};
        insertApprovalProcesses(userList[PENDING_SUBMITTER], userList[APPROVED_SUBMITTER], pendingPlan, approvedPlan);
    }
    private static void insertApprovalProcesses(User pendingSubmitter, CustomObject__c pendingObj) {
        List<Approval.ProcessRequest> requestList;
        List<Approval.ProcessResult> resultList;
        Approval.ProcessSubmitRequest request;
        
        requestList = new List<Approval.ProcessRequest>();
        request = new Approval.ProcessSubmitRequest();
        request.setObjectId(pendingObj.Id);
        request.setSubmitterId(pendingSubmitter.Id);
        requestList.add(request);
        resultList = Approval.process(requestList);
        for (Approval.ProcessResult result : resultList) {
            System.assert(result.isSuccess(), 'Failed result: ' + result);
        }
    }

@IsTest
static void test() {
        Id pendingApproverId = getUser(PENDING_APPROVER).Id;
        Set<Id> approverIdSet = new Set<Id>{ pendingApproverId };
        List<String> PENDING_STATUSES = new List<String>{null, 'Pending', 'Started'};

        // When
        Test.startTest();
        Map<Id, ProcessInstanceWorkItem> resultMap = [
            SELECT Id, ActorId
            FROM ProcessInstanceWorkItem
            WHERE ActorId IN :approverIdSet
            AND ProcessInstance.Status IN :PENDING_STATUSES
        ];
        Test.stopTest();

        // Then
        System.assert(!resultMap.isEmpty());
}