My point of view is that there is no inherent problem in using either construction. If you adopt a modicum of categorical language, then you can define the set of ordered pairs in either way, then define 'function as subset with extra properties', define composition. Until that point you have no way of comparing sets, so cannot say within the language that the two Cartesian products are different (Can one say different before one can say 'the same'?) The categorical point is then that 'product' is defined by a universal property and so is determined up to isomorphism (bijection) only, hence having two different models with the same property is no big deal.

You may not want to introduce categorical language, but realising there is no problem and that set theoretic ideas cannot tell the difference between two 'different' but bijective sets seems to be a step towards a solution to your conundrum.