The Gemara quotes the Pasuk from Shmuel I 26:19 "Behold I was banished today from dwelling in the inheritance of Hash-m ...", and Rashi says that David Ha'Melech is alluding to the future when he would have to escape to Moav and to Achish.
This is difficult since Pelishtim is part of Eretz Yisrael, and Tziklag, where David lived at the time, was part of the portion of Shevet Yehudah. Likewise, Yitzchak was commanded not to leave Eretz Yisrael, yet he lived in Gerar in Pelishtim.
A. Schwartz
Many sources assume as you do that David Ha'Melech was in Pelishtim when he said these words in Sefer Shmuel. Close examination of the Pasuk however reveals that David said these words to Shaul in Midbar Zif - the Judean Desert - certainly not in Pelishtim. (I would qualify this by noting that there are those who maintain that parts of Pelishtim extended into the land of Yehudah, and it is possible that Shaul pursued David in this part of Midbar Yehudah.)
The Radak relates to this question and says, "for they are banishing me from dwelling in the inheritance of Hash-m to dwell among idolaters. Even though he had not yet left the land of Yehudah, he was aware that he would have to do so. He knew that he would not succeed in eluding Shaul if he was to remain in Eretz Yisrael. He escaped to Achish the king of Gat (Shmuel I 21:11), and he also went to Mitzpeh Moav and brought his father and mother before the king of Moav where they remained (Shmuel I 22:4), even though David and his men returned to the land of Yehudah".
The Gemara is clearly referring to David Ha'Melech's physical exile from Eretz Yisrael. There is a dispute about those parts Eretz Yisrael specified in Bamidbar 34 that were not yet conquered by Yehoshua or the generations that followed. The Hagahos Ya'avetz (Kesuvos 110b) proves from your question that even though Pelishtim is within the borders of Eretz Yisrael, it is nevertheless considered Chutz la'Aretz since it was not conquered when the Jews entered Eretz Yisrael. Based on his understanding, we may assume that the borders of Eretz Yisrael in time of the Patriarchs were determined by Bamidbar 34 and not by what was actually conquered at the time of entry into Eretz Yisrael.
It is also possible to resolve your question based on the Igeres Ha'Shemad of the Rambam who says that there is no doubt that Pelishtim is within the boundary of Eretz Yisrael. The Gemara that says that "all who dwell outside Eretz Yisrael is as if they have no God" results from dwelling in the midst of idolaters and being subject to their influence, even though they are technically living in Eretz Yisrael. (Perhaps we can infer this from Rashi who says (Bereishis 26:12) that even though Pelishtim is part of Eretz Yisrael, it lacks the importance of the rest of Eretz Yisrael.)
There is a great deal more to this topic, but these are the main points.
Aharon Steiner