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.

This is an assumption though, and in lieu of hard evidence it seems that testing would be the best way forward.


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