However, on investigation I was finding that If I logged on as them, and went to edit a page, the "Parent" field for the page was being changed - with "None" not being an option. Obviously a permissions problem... but what?
The solution was in the permissions for that user's group - You have to have "Manage All Content" selected. I found this by trial and error and still don't know why that particular permission is required to stop the page index getting messed up. One would have thought that the parent wouldn't change if this permission was not set. Perhaps someone nice out there will "pity this damn fool" and tell me.