**The criteria is not checked again in this situation - see below**

According to the [Time-Based Workflow FAQ][1], any record which no longer matches the criteria for a time-based workflow will be removed from the queue. This is vague though and doesn't indicate whether a test is performed if the other record is updated.

I would expect that the criteria would work like a formula field, and that the system would at least check for validity when the timer elapses before executing anything, discarding the record in the process - but it seems like I am wrong.

**Test Results**

I ran a test to see if the criteria would be evaluated again before the workflow actions took place, and it seems like no check is performed.

When changing a field on the second object such that the criteria would not be met, the first record stayed in the queue which is to be expected.

However, the field update I specified was still performed once the time-based rule was processed. 

**Work Around**

If you update the record that's queued such that it doesn't meet the criteria for the work flow, *it is removed from the queue*. An extention of this is that if you modify object B so that A would fail and then perform a non-changing edit on A (i.e. hit edit and then save) it also gets removed on the queue.

The upshot is that you could create a trigger on B after update, to perform a non-changing edit on all child records (object A) of the records being run through the trigger. This should in turn clear out the non-conforming records from the queue and prevent the workflow field updates etc. from taking place.

  [1]: https://help.salesforce.com/HTViewSolution?id=000005245&language=en_US