Tom,
Yes the machines are all joined on the domain, and we do not use any proxy configuration using wpad.
It's Like Jkay said, the Cisco Anyconnect client is adding the ".co.uk" suffix to the DNS Search list, but only when it is connected. I can remove the entry manually form the adaptor settings when connected and everything is fine. As soon as the VPN re-connects the extra suffix is added back again.
I have gone over our Cisco configuration, I can find our main company domain entry but there is nowhere I can find the ".co.uk" entry.