Take them to the cleaners. You have the documented proof and the hotel owner (independent witness), you can be sure there are plenty of firms who will specialise in this sort of case and freely advise you which correct action to take. My bet is "they" will want to settle quietly, which may go toward the staff Christmas do
On another note: The low all in prices are often thrown in by firms to get the service co. in the door. The large balloon lot who pay my wages probably do it to get contracts in all services - mechanical/electrical/security often as a loss leader. I'm convinced the specific part of the department (Ansul servicing) I work in doesn't make a penny, quite the opposite probably! But the hierachy must obviously look at the bigger picture, all the clients are large nationals and of the "all in" type so following the all disipline service and new installs on an annual basis there will be a viable profit margin.
There is plenty room for the smaller co.s out there but where the big boys walk in with these crazy loss leaders (Iv'e spent many years servicing exts and trying to fight these prices) everyone loses out. The smaller guys have to beat these prices and inevitably service quality diminishes.
My philosophy was always pretty simple: You get what you pay for. Sometimes worked, sometimes not, but I don't believe in dropping standards to win or keep a contract.