I would start by going to the company and saying that you have this check for them. If they do the work, they can have the check. If not, they can't. If they still won't do the work, find out why. Let the next company know if it's work related (e.g. extra difficulty due to something not immediately obvious).
Once you've exhausted that, get new quotes from several companies. Get a binding agreement to do the work. Then go back to the seller for a replacement check. That conversation will be a lot easier if the new check is for the same amount or less than the old check. Consider the possibility that it would be easier to get a check made out to you in the original amount.
If the seller won't give you a replacement check, you might have to talk to a lawyer to achieve anything more. If you have a written contract with the company that was going to do the work, you might be able to sue them. Possibly you give them their check and they give you money (cash, check, whatever) in return. Perhaps they do the work after all. Depending on your agreement with the seller, you might be able to sue there instead. This is not a great option, particularly if the amount is small.
If you can make a deal with the company or the seller, that is better than suing. At some point, suing is mostly throwing away money, as the lawyer will cost money. For $100, it's not worth it. For $1000, it's questionable (consider small claims court). For $10,000, then maybe a lawyer. Part of the problem though is that you really need a lawyer to read the documentation for this.