Since the two papers together prove one main theorem (if I correctly understand the first few lines of the question), it seems reasonable to submit them to the same journal. I can imagine a referee or editor being unhappy about being asked to publish part 1, which builds up to a big theorem that will appear in a different journal.

It's true that it can be hard to find room in a journal for very long papers, but I assume the journal doesn't mind publishing papers of 50+ pages at least occasionally (otherwise you wouldn't have sent part 1 there), and the difficulty of finding space is no worse for two of your papers than for one of yours and one of someone else's. The main effect of space shortage in such situations is that the two parts of your paper might appear in different issues of the journal.

I've published multi-part papers with all parts in the same journal. The splitting into parts was forced by the journal's upper bound on the length of papers, but I don't recall any complaints from the editors about my submitting several parts, each close to the upper bound. In at least one such case, the parts ended up appearing consecutively in the same issue of the journal. (The only time I've submitted "parts" to different journals was when they were really separate papers, though on the same topic. Two parts were really logic and appeared in the Notre Dame Journal of Formal Logic, and one part was, at least in my opinion, of broader interest and appeared in the AMS Transactions.)