Ok, tried lots of things ... but please answer this question:
Does your site have links like:
on it's? Yes or No?
Something either in config of apache server (rewrite rule?) or Moodle OR network (as Dan has also suggested) is injecting (tacking onto the end of them) the '&MoodleSession=blah blah blah' in the URL's.
Mind providing the URL to your Moodle front page?
'spirit of sharing', Ken