TL;DR
Contract disputes are a way to manage financial risk to the company, not schedule risk. As a purely practical matter, you can't really transfer schedule risk away through contractual means, no matter what the contract may say.
In the short term, your immediate options will be based on a business analysis of your company's needs and alternatives. Also, keep in mind that the selected option is more likely to be based on political decisions by senior management than anything else.
Identify the options and associated costs, and present them to management for a decision. Then focus on fixing your processes for the future.
Brooks' Law Applies Here
Is there a fair way of deciding when the vendor should "eat" the unforeseen level of effort and when the customer should, indeed, pay more?
While some answers may address this legalistically, or discuss the benefits of the agile principle of customer collaboration over contract negotiation, at heart you're simply asking the wrong question.
The pragmatic question in any such dispute should be: Do I need the outcome more than I need the original agreement or payment terms? At the end of the day, while both sides can assign blame, affix responsibility, or lawyer up, none of these things actually get work done. Even if you're willing to walk away from your relationship with the vendor, you are then faced with hard choices about who will do the work, how soon they can actually deliver it, or whether you can get the end result you need at all.
Brooks' Law often applies here, because your project is likely already late. Disputing contracts, switching vendors, or seeking alternative solutions at this point may make your project even later. Whether or not this is acceptable from a business point of view is ultimately a strategic or risk management decision, rather than strictly a contractual one.
Fix Your Process and Controls
You can't really undo the damage at this point, because all your options will either cost more, reduce scope or quality, or delay your product delivery. Maybe all of the above. However, you can analyze the process failure, and aim to do better next time.
In most such cases, the problem isn't actually contractual. The real issue is that the business didn't learn about a problem until it was too late. Agile processes address this through continuous collaboration, transparency, and tight inspect-and-adapt cycles.
It's generally much better to implement fail-fast project controls so that you can either adjust the project or terminate it early before incurring excessive sunk costs or finding yourself facing the dilemma of whether or not to chase sunk costs. Whatever process or control failure allowed the project to reach this juncture without lots of forewarning that your budget or target dates were at risk is flawed, and should be adjusted.
At the end of the day, even if the company "outsourced" the work on its software project, someone internal to the company is still responsible for the delivery of that project. Pragmatically speaking, if that person breaks the project, they get to keep both halves.