Lost checks happen occasionally, and there are procedures in place (banking & business) to handle the situation. First and foremost you need to:
- Contact the company as soon as possible and inform them that you no longer have the physical check. You should request that they void the old check at their issuing bank (so that if a criminal attempts to cash or deposit it, the bank can react appropriately). This might take a couple of weeks to process, or might have fees and procedures to follow from the bank.
- Once the check has been voided, request that the company reissue you a new check for the security deposit. This might involve fees from the company (processing, mailing, bank fees, etc); however this is preferable to forfeiting the funds altogether.
Note: The money is legally yours, so the company is obligated to work with you here. If they refuse to cancel or reissue the check, at a minimum you'll want to contact the state government and let them know about the company's actions, if small claims court is not an option. Businesses aren't permitted to keep 'forfeited funds' in most states, instead they are required to turn them over to the government who would then return them to you when you ask for it. It's rather scummy of the government bureaucrats, because it puts them in the sole position to benefit from forgotten money, but that's the system we've given ourselves.
- Once the new check has been issued, this now becomes your primary job to wait for and deposit the new check as soon as it arrives. You have the benefit of the doubt for the first lost check, but if you lose a second copy then your credibility quickly disappears.
Since you've moved overseas since the last time you worked with this company, you might need to exercise a little patience and be willing to jump through some hoops to get this resolved. Be prepared to provide them proof of who you are, and be ready to pay for extra security such as certified mail / FedEx so that you're both sure that the new check is delivered to you and only you.
Last of all, learn from your mistake this time and be a little more cautious / proactive in keeping track of checks and depositing them in the future.