**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. 

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