I hate to disagree with you all, and perhaps I'm really missing something, but this seems to work for me:

Note: On Lead, I've created a field called "RunReassignmentRule__c as a boolean which I set when I want the assignment rules applied.

If adding a field is a problem using the third party app, you could instead overload a field.  For example, if "Company" is set to "XXXX_CompanyName", then apply the assignment rule and reset the Company name back to it's proper form.

I'm sure you get the idea.  Best, Steve.

Trigger:

trigger AssignmentRuleOnRatingChange on Lead (after update) {
	if (Utilities_RecursionControl.weAreAlreadyProcessing()) return;
	Database.DMLOptions dmo = new Database.DMLOptions();
	dmo.assignmentRuleHeader.useDefaultRule= true;	
	List<Id> leadIdsToAssign = new List<Id>();
	for (Integer i=0; i < trigger.new.size(); i++){
		if (trigger.new[i].RunReassignmentRule__c){
			leadIdsToAssign.add(trigger.new[i].id);
		}
	}
	if (leadIdsToAssign.isEmpty()) return;
			
	// Reload Leads, yes, in mid-update, as we can't use the instances in trigger.new
    List<Lead> leadsToAssign = new List<Lead>([select id, RunReassignmentRule__c from lead where id in :leadIdsToAssign]);
    for(Lead l: leadsToAssign) {
    	l.setOptions(dmo);
    	l.RunReassignmentRule__c = false;
    }
    Utilities_RecursionControl.disallowFurtherRecursion();
    try {
    	Database.Update(leadsToAssign);
    } catch (Exception e) {
    	system.debug('Exception in AssignmentRoleOnRatingChange: ');
    	system.debug(e);
    }
    Utilities_RecursionControl.resetRecursion();
}

Utility class for Recursion:

public class Utilities_RecursionControl {
	// Steve Bower  5/6/2009    sforce@stevebower.com
	// See page 150 of the Workbook on how to control Trigger recursion.
	private static Boolean alreadyProcessing = False;
	public static Boolean weAreAlreadyProcessing() { return alreadyProcessing; }
	public static void disallowFurtherRecursion() { alreadyProcessing = True; return; }
	public static void resetRecursion() { alreadyProcessing = False ; return; }
}

 Test Code:

@isTest
private class Test_AssignmentRoleOnRatingChange {
	// SBower 10/10/2010
    
    static void doCheck (Lead lead, String rating, String queueName){
    	Lead checkLead = [select LastName, Company, Rating, RunReassignmentRule__c, ownerId, owner.Name from Lead where id = :lead.id limit 1];
    	system.assertEquals(rating, checkLead.Rating);
    	system.assertEquals(false, checkLead.RunReassignmentRule__c);
    	system.assertEquals(queueName, checkLead.owner.Name);
    }
    
    static testMethod void TestReassignments() {
    	// Since I can't set up Assignment Rules in my test code, I have to run using the Groups and Rules that are already extant.
   	
        // Create a few groups.
        List<Group> groups = new List<Group>([select id, name from Group where name like 'Assignment %' and type='Queue' order by name asc]);
        // This should give me my four groups, 'Assignment A', 'Assignment B', 'Assignment C', and 'Assignment D'
        system.assertEquals(4,groups.size());

		
		// Let's create some new Leads
        // Assignment means the OwnerId of the Lead is set to the Group's Id.  So, default them all to Group A.
        // Note: I'm not setting the Rating field value.
        // Note: I'm not setting the RunReassignmentRule__c value;
        
        // My Assignment rules are:
        // If Rating = 'Hot' -> Assignment B
        // If Rating = 'Warm' -> Assignment C
        // If Rating = 'Cold' -> Assignment D
       
		List<Lead> leads = new List<Lead>();
		leads.add(new Lead(LastName = 'AAA', Company = 'Test_AssignmentRoleOnRatingChange AAA', Status = 'Open - Not Contacted', ownerId = groups[0].id));        
		leads.add(new Lead(LastName = 'BBB', Company = 'Test_AssignmentRoleOnRatingChange BBB', Status = 'Open - Not Contacted', ownerId = groups[0].id));       
		leads.add(new Lead(LastName = 'CCC', Company = 'Test_AssignmentRoleOnRatingChange CCC', Status = 'Open - Not Contacted', ownerId = groups[0].id)); 
		insert leads;      
		system.assertEquals(3,[select count() from lead where Company like 'Test_AssignmentRoleOnRatingChange %']);

        // Ok, so let's do some testing.
        // Start by setting the first three to each of the three ratings, and trigger the assignment.
        leads[0].Rating = 'Hot';
        leads[0].RunReassignmentRule__c = true;
        update leads[0];
        doCheck(leads[0], 'Hot', 'Assignment B');
        
        leads[1].Rating = 'Warm';
        leads[1].RunReassignmentRule__c = true;
        update leads[1];
        doCheck(leads[1], 'Warm', 'Assignment C');
        
        leads[2].Rating = 'Cold';
        leads[2].RunReassignmentRule__c = true;
        update leads[2];
        doCheck(leads[2], 'Cold', 'Assignment D');
      
        leads.clear();
        leads.add(new Lead(LastName = 'DDD_0', Company = 'Test_AssignmentRoleOnRatingChange DDD_0', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_1', Company = 'Test_AssignmentRoleOnRatingChange DDD_1', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_2', Company = 'Test_AssignmentRoleOnRatingChange DDD_2', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_3', Company = 'Test_AssignmentRoleOnRatingChange DDD_3', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_4', Company = 'Test_AssignmentRoleOnRatingChange DDD_4', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_5', Company = 'Test_AssignmentRoleOnRatingChange DDD_5', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_6', Company = 'Test_AssignmentRoleOnRatingChange DDD_6', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_7', Company = 'Test_AssignmentRoleOnRatingChange DDD_7', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_8', Company = 'Test_AssignmentRoleOnRatingChange DDD_8', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		leads.add(new Lead(LastName = 'DDD_9', Company = 'Test_AssignmentRoleOnRatingChange DDD_9', Status = 'Open - Not Contacted', ownerId = groups[0].id));
		insert leads;
		
		// Check small bulk
		for (Lead l: leads) {
			l.Rating = 'Hot';
        	l.RunReassignmentRule__c = true;
		}

		// verify that there are no Leads assigned to the 'Hot' queue from this batch, and that they are all in Queue A
		system.assertEquals(10,[select count() from lead where Company like 'Test_AssignmentRoleOnRatingChange DDD%' and owner.Name = 'Assignment A']);
		system.assertEquals(0,[select count() from lead where Company like 'Test_AssignmentRoleOnRatingChange DDD%' and owner.Name = 'Assignment B']);
        update leads;
        // verify the Assignments are done.
		system.assertEquals(0,[select count() from lead where Company like 'Test_AssignmentRoleOnRatingChange DDD%' and owner.Name = 'Assignment A']);
		system.assertEquals(10,[select count() from lead where Company like 'Test_AssignmentRoleOnRatingChange DDD%' and owner.Name = 'Assignment B']);    
   
    }
    
}

Of course this isn't perfect, especially as far as the recursion control goes. Critical sections would be nice; you might  want to create a use-specific version of the Utility class, and perhaps even a user-specific check within the class to further restrict the possibilities for conflict.