There are some heterogeneous binary operations implemented already. For example 10**400 < float('inf') correctly returns True even though there's no type in Python to which both values could be losslessly coerced to perform that comparison.
I don't think adding a few more cases like that implies an obligation to fix every case. It's a "perfect is the enemy of the good" situation.
I disagree with your notion of conceptual complexity. The conceptually simplest thing to do is to perform the requested operation exactly and then round if necessary. Only practical difficulties prevent that from happening in all cases. It's not conceptually simple to convert int to float and float to complex blindly regardless of the consequences. C99 gets complex * real multiplication right, despite C being the poster child for numeric promotions, and so does C++. It isn't hard to get it right, and programmers would be happier if Python got it right. Programmers don't expect or want consistent promotion to complex even when it breaks things.