Tackling it directly and amicably hasn't been effective so tackling it through their webhosting company using the legal process is likely to bring a very swift response and strongly discourage them from continuing to do this. The DMCA is the best and fastest approach in my view and applies in the UK, US and EU. It's also free (more on this later).
The relevant UK law is the Designs, Copyrights and Patents Act
This states that assigning copyright permissions fully or partly to others must be done in writing. Unless there is clear evidence of this, which can be in an electronic form (eg Creative Commons licensing) then they have no permission to use it. It applies to any 'works' including Images or digitalwork created by UK citizens. Copyright is also transferred automatically if necessary (eg upon death of the original creator of the work).
Damages may be payable and this is far more likely if there has been flagrant infringements with advance knowledge of the fact it was illegal. Your previous communications with them provide clear evidence of this. Many different actions can be taken against the company including include Court Orders against the web hosting company as well as the company themselves.
The service provider can be found via a service like http://who.is and contacted directly. This is a requirement for all websites.
The UK, EU and US comply with the DMCA laws which are very fast and do not need any legal input or third party assistance. This is particularly useful if the webhosting company is in the US, EU or US for the company who is infringing your copyright. All major social media sites remove content when a DMCA notice is filed, normally without any investigation. Web hosting companies are required to remove or suspend access to the image quickly in order to avoid being held legally responsible themselves (see link above).
You can file a DMCA takedown request - the hosting company can be notified of each infringement rather than directly notifying the company. Repeat infringements are likely to be taken seriously by the hosting company, which may terminate their account (or threaten to do so). DMCA does not require a formal copyright to be claimed in advance for you to prove it has been broken.
The company can file a counter-notice once the webhosting company sends the DMCA to them - thish involves them prooving that they have a legal right to the image, for example proof that it has been licensed under Creative Commons or released as a Public Domain image (which again requires proof that you actually did this). Copies of previous notifications that they must remove it count in your favor combined with the fact that have repeatedly removed it in the past, plus the fact you published it first and it clearly was produced for your company.
Most hosting companies have a legal agreement with their clients allowing them to terminate accounts of repeat offenders, e.g. godaddy's Legal Agreement, sections B and D state this. All this is free, but a strongly worded letter from a lawyer may also be effective.
The threat of losing their website or paying to move to another hosting company, and the disruption that will cause, is likely to have a major impact. If they have had brochures or leaflets printed including the photo they will need to stop distributing them because continuing to do so is further copyright breech.
Depending on your company's view you could also add a disclaimer to your website stating that you do not promote any other companies (except when mentioned directly on your website). Most company websites clearly have
© Copyright information at the bottom but this isn't a requirement for legal protection.
If the company has a blog or newletter then a brief entry about legal action being taken against company X could be written explaining you do not endorse the company and have taken legal measures (they cannot have this removed since 1. it's true, 2. it's not illegal to disclose the information- if it damages their reputation they are the ones at fault- it doesn't count as copyright violation or privacy violation to disclose legal stuff or opinions).