W wyniku rozpadu po 1204 roku Cesarstwa Bizantyńskiego na szereg drobnych zwalczających się państw zniknął najpotężniejszy przeciwnik niewielkiej Kefalenii. Jednak już w 1206 roku pobliską Korfu zajęli Wenecjanie i podjęli próbę uzależnienia od siebie Kefalenii. Maio Orsini uznał się wówczas za podległego papieżowi, ostatecznie jednak dwa lata później musiał uznać zwierzchnictwo Wenecji. Około 1213 roku znajdujące się w ręku weneckim Korfu i Dyrrachion zdobył Michał I Angelos, pierwszy władca Epiru.
Od tego czasu datują się ściślejsze związki Maio Orsiniego z Epirem przypieczętowane ślubem z siostrą Teodora Dukasa Komnena, Anną. Jednocześnie Maio nie zaniedbywał związków z Hohenstaufami. W 1228 roku podejmował u siebie udającego się na wyprawę krzyżową Fryderyka II Hohenstaufa. Rok później poprowadził mu na pomoc siły przysłane przez Teodora Dukasa Komnena, wówczas już cesarza Tesaloniki. Związki z Angelosami trwały do 1236 roku, kiedy władca Wysp Jońskich uznał zwierzchnictwo Księcia Achai, Godfryda II Villehardouina.