The obvious suggestion is to register with the Telephone Preference Service.
http://www.mpsonline.org.uk/tps/
If they have requested VM to stop then, as I understand it, there are obliged to do so. If they do not then I would make contemperanious notes of any conversations and then approach your local trading standards.
http://www.tradingstandards.gov.uk/