Diddy: I did take the phone back to the shop and showed them the situation. They took it back in, said they opened it back again, cleaned both sides of the glass on the cover and the lens (i.e. everything that could be cleaned) and looked at it under a microscope. No change! Which is why I suspect it is on the image sensor. Though I am perplexed how anything could have got on to the image sensor (in the process of the battery being changed) if it is hard to reach .
SMvim: See pics in my post # 5 above. The lens is actually accessible (staring right at you!) when you open the back cover. You can see that in Step 9 of the link you provided. But I didn't know where the sensor was - if it's internal to the module, then it certainly is hard to access. But as I mentioned, how did dust or something get in there then? Yes, the phone is in a case with cut-out gap for the camera. I've taken it out of the case as well (to give it to the shop for the repair), so can safely rule out the case.