Hi all,
For completeness, in case anyone else finds and reads this thread.
After discussions with our name server provider, there was little feedback or support on the problem, so we took the decision to move provider and the problem has since stopped.
Many thanks for the friendly support.