This had to go all the way to L3 before we got the fix.
Apparently, when running ST on a Linux server 3 extra lines need to be added to the sametime.ini to ensure browsing is stabilised:
UCM_LOCAL_IP=<server ip address>
VPS_BIND=<server ip address>
VPMX_IP=<server ip address>
A recycle of both servers - het presto! problem fixed!
Of course, the question that will remain unanswered is why did it work for months without these settings invoked?