Well the problem does not go away. I have tried purging all caches, restarting dns servers and clients, and nothing has changed.
Using my iphone as the test client - if I connect to the network via wifi, and go to our Moodle homepage, a page loads as if I am another user - but with almost no functionality (links don't work etc, I get in a cycle of logging in/out).
If I turn off wifi and connect via phone coverage (therefore external connection to our Moodle server) everything is fine.
So - something tells me it is a network issue that is not playing nice with our Moodle setup. Any ideas?