Finally, I could seek to enforce the policy on the other professor, but as mentioned, it's not clear how one does that, especially if the other professor is in a different department. (And since it's often relatively senior professors doing this sort of thing, at that point I worry about negative repercussions.)
I see no alternative to "enforcing the policy on the other professor". Seniority does not confer the right to violate university policy. In my opinion you should not let hypothetical concerns about your career or your tenure case stop you from standing up for your students in a situation in which policy is clearly on your side: assistant professors are university faculty, not captives who hope to be rewarded in the future for their docile behavior.
The way to bring it up is to communicate with the other professor as soon as possible. I would recommend speaking in person or over the phone, as email renders trivial a large variety of passive-aggressive behavior: e.g., they might not respond at all, leaving you to wonder how long to wait. If you talk to someone face-to-face they have to either be reasonable or display their unreasonableness directly to you. How do you look another faculty member in the face and say "I'm sorry that students will be missing your midterm, but it is critical that my midterm last double its scheduled length"? You should come to the meeting knowing the relevant policy cold. You should bring printed copies of the policy, but only take them out if things are not going your way.
You should continue talking to this person until you have conveyed that their proposal is against the policy, is specifically detrimental to your course, and that students are being caught in the middle. If they agree to that or at least acknowledge receipt of the information and still are intransigent, then you should end the conversation, calmly, by saying that you will have to take the situation up with the administration.
I would then bring the matter to your department head and see what is suggested. If the faculty member is in a different department then it may be in order for the two department heads to have a discussion. If the department head does not take ownership of the issue you should ask whether he [I happen to know that the head of the OP's department is a "he"] wants you to take up the issue with the higher administration. If not, then as an assistant professor this may be the place to drop it, but again you should communicate clearly that policy is being violated and students are suffering. Or you could take it up with the higher administration: I might have done that as an assistant professor. (As a tenured associate professor I would probably do it now, and would not worry about it jeopardizing my future promotion or dealings in the department. On the other hand, the egregious behavior you described would probably not even be attempted at my large public university.) Tenure and promotion is not a docility contest, and "He reported a rule violation" is not a point against someone's case. I think honestly the issue is mostly one of your own peace of mind, so act accordingly.
You certainly have my sympathies: it sounds like the other professor is being both selfish and unreasonable. It's hard to deal with unreasonable people -- you just can't reason with them! -- and if a situation arises in which it is primarily a battle of wills, then the unreasonable person tends to take the outside track. The fact that you care about the students and the other guy apparently really does not could indeed make you blink first. You may for instance end up having to give a makeup exam to some of the students. If so you should clearly document every time you do that and have the individual students vouch for you as well.