I believe that the corpse of a gentile is not metameh. If so what was the fear of the graves outside of Israel. I would imagine that the Jews outside of Israel were careful in marking graves.
Kol Tuv,
Eli Turkel
(a) TOSFOS (15b, DH v'A'avira) writes in one answer that granted, the Rabanan did not decree Tum'ah on the airspace of the land of the gentiles; they only decreed Tum'ah on touching and carrying the dirt (for the corpse of a gentile is Metamei if one touches or carries it; it is just not Metamei b'Ohel).
This answer is difficult to understand, though, because it comes out that Rebbi Shimon is arguing with the Rabanan who lived eighty years prior to the Churban, and who long preceded Rebbi Shimon (one would have to say that Rebbi Shimon holds that the Rabanan never made a decree on the airspace of gentile lands).
(b) However, TOSFOS in Nazir (54b, DH Eretz ha'Amim) writes that the decree of Tum'ah on the land of the gentiles was (1) because of the large number of Jews that were killed in Chutz la'Aretz, or (2) because of the gentiles who died before the Torah was given, whose corpses indeed are Metamei (as Tosfos writes there in Nazir 54a, DH O b'Kever), or (3) perhaps the Rabanan were stringent regarding the airspace of the land of the gentiles so that Jews would not leave Israel to go Chutz la'Aretz.