Whole bike is only 3 months old, and in that time has done about 600 miles. I went for another test ride after getting an idea, and I think it only creaks on one side of the left pedal (they're double-sided Shimano M520s) which explains why the noise went on the test ride before this one. It doesn't creak if I pedal unclipped on the left either, even if I put some power in.
The click noise still wasn't there though, and I'm so relieved for that. At least I know where the creak is coming from.
The thing is, the creak is temporarily cured with a bit of grease on the plate that hooks onto the cleat, which makes me question if it could really be more involved than that. But I've never seen pedals come with grease on that particular bit of metal, so it's odd that it needs the grease at all.