I think that's it! I should have realised that there would be one execution plan for the "If Exists () Or Exists ()" statement rather than two.

If I have the chance, I'll try to get execution plans but, given it's on a client's live database (and, so far, it's not been reproducible here, even with a restore of their database), this is unlikely.