Is this "lose" as in "to not be able to find", or as in the opposite of win?
The latter meaning. Lose here means to fail.
"Công ty của bạn mất hợp đồng đó" means that your company fails to sign that contract. Another company got it.