Из остальных социалистических стран наиболее успешно сложились отношения Святого престола с Югославией. Начиная с 1964 года вновь возобновились переговоры между обеими сторонами, в результате чего в 1970 году были установлены и дипломатические отношения. В 1970 году Павел VI принял на официальной аудиенции в Ватикане президента Тито.
С Польшей нормализация отношений протекала сложнее, что зависело скорее от польского государства, чем от Ватикана. Начиная с 1966 года Казароли несколько раз приезжал в Польшу; вначале он вел переговоры с руководителями польской церкви, а с 1971 года начались переговоры и на правительственном уровне. Результат вскоре не замедлил сказаться: в 1972 году Павел VI назначил новых епископов в епархии Западной Польши, тем самым признав границу по Одеру — Нейсе. (В то же самое время в Польше стало уже три кардинала!) 1 декабря 1977 года Павел VI принял на личной аудиенции польского руководителя Эдварда Терека; темой их переговоров было дальнейшее урегулирование взаимоотношений между польским государством и польской церковью.
С Чехословакией также проводились переговоры, начиная с 1973 года — без особого результата. В 1973 году здесь тоже были назначены новые епископы. С Румынией, располагающей католическим меньшинством, у Ватикана нет тесных отношений, хотя в 1968 году премьер-министр Маурер, а в 1973 году президент Чаушеску нанесли визит Павлу VI. В итоге начавшихся с ГДР переговоров в 1973 году здесь тоже смогло состояться назначение новых апостольских администраторов.
Во взаимоотношениях Ватикана с Венгрией новый этап открывало будапештское соглашение от 15 сентября 1964 года. (Это соглашение касалось модернизации процедуры назначения епископов.) Фактором, отрицательно сказывавшимся на улучшении этих отношений, было дело Миндсенти, а точнее, нежелание идти на какой бы то ни было компромисс кардинала Миндсенти, убывшего во внутреннюю эмиграцию на территории американского посольства. Взаимное терпение и доброжелательство к концу 60-х годов дало свои плоды. В 1969 году в Венгрии было одновременно назначено 11 высших священнослужителей (архиепископов, епископов, администраторов). Новые переговоры начались осенью 1970 года; результатом их было и решение проблемы Миндсенти. Венгерское правительство в 1971 году дало согласие на выезд Миндсенти за границу. (В конце концов он поселился в Вене, в Пазманеуме, и в уединении занялся написанием мемуаров.) Затем в 1972 году последовали новые назначения епископов. 5 февраля 1974 года Ватикан публично заявил, что папа Павел VI объявил вакантным место эстергомского архиепископа, а кардинал Йожеф Миндсенти был переведен на пенсию (кардинальский сан был, разумеется, за ним сохранен). Упорно сопротивлявшегося ходу истории и смягчению международной напряженности престарелого кардинала папе пришлось буквально вынудить к отставке, не в последнюю очередь и в интересах венгерской церкви. (Для ухода в отставку, вообще говоря, наличествовали и канонические условия — ведь Миндсенти было уже 75 лет.)