You keep saying that, but it is different.

If the company paid you cash and you lost it, the company no longer has the money. The money left their account. If they had $1,003,500 before they paid you, now they have $1,000,000.

In the OP's case, they paid him with a cheque he never cashed. So after they "paid" him, they still had $1,003,500 in their account. Now, months/years later, they still have the $3,500.

You keep saying "it's not different," but clearly, it's exactly $3,500 different.

Let's say they write him another check and he loses that. Then another and it falls in the fire. Then his dog eats it. Do they have to keep writing checks?

No. They gave him a valid payment with conditions attached (cash it by XX/XX/20XX). He accepted it. Now he doesn't like the conditions because he didn't do his part.

Look, I am sympathetic to the problem and I see no reason not to ask for a new check, it's what I would do. But I don't think he has much of a legal leg to stand on, even if the details are different from having received cash.

I hope the poster does not listen to Doinghomework and contacts the company so a new check can be re-issued. What if he never received the check, which was extremely likely given he moved and was out of country? Does that mean the company has made good on their payment? No. they need to re-issue the check.

Contacting the company will be of no help here. The OP said they are out of business.

It seems the OP has edited the OP. (Where OP and OP stand for Original Poster and Original Post.) The company is out of business. One of the principals initially offered to make good on the company's obligation, probably out of his personal funds; but then it seems that when he learned the amount, he changed his mind. It is unlikely that the OP will be able to resolve this issue from another continent. It also seems unlikely (given the additional information that has been shared) that the account the check was drawn on is still active. And even if the debt were legally owed, it's pretty hard to collect from a business that is no longer in business; depending on how it was structured, it's theoretically possible that the company officers would be personally liable for the company's debts, but again that seems unlikely.

At this point the OP's only option seems to be to sell the debt to a debt collector at pennies on the dollar, and let them threaten the former company over the unenforceable and ethically debatable debt obligation.

Whoa...I suggest he DOES contact the company and ask for a new check. I'm just saying that the company really has no obligation to give it to him.

If he never received the check then that would be different. In this case he admits he has and has already told the company.

Well re-reading the original post, how the original company closed up shop, closed it's books/accounts he may be out of luck. It's kind of like a company going bankrupt.
bummer for him. At this point, have to rely on the moral code of someone connected with original company honoring past debts. A lot of money to leave on the table.

A vaguely relevant blog post: http://www.fivecentnickel.com/2012/04/23/how-long-are-undeposited-checks-good/

Since the company got the service and never actually completed payment for that service, there are a number of equitable theories (e.g., unjust enrichment) that a judge could apply here to get the OP payment if the company hadn't gone out of business.