The check that has not been returned by the 2nd/other customer should be payable to the 1st customer, right? Therefore, they will have to forge an endorsement to be able to cash the item. I would definitely let all tellers know about the check in case they try to cash at the bank and would place the stop payment instructions so the item will reject if it comes in transit, you can then return the item based on improper or forged endorsement. It is possible however, that the customer you are unable to contact is out of town and completely unaware of the situation. I would be less concerned with a loss if the check somehow manages to pay, unless it's a significant amount, and more concerned about customer privacy. I would definitely review controls/procedures for this process also.
_________________________
An error is not a mistake until you refuse to correct it