Martyn, the fact that one of the users with a problem uses NTL may be a clue - NTL force the use of transparent caches (one of the reasons I ditched them).
You may want to ask which ISPs the users with problems connect through.
You may want to ask which ISPs the users with problems connect through.