A large part of Shimon lived in Yehudah's boundaries, true (as described in Josh. 19:1-9). But in I Chron. 4:31, after (more-or-less) the same list of cities is repeated, the verse adds a crucial detail: "These were their cities until the reign of David."
Pseudo-Rashi and Metzudas David explain that in this period the Tribe of Yehudah's population increased so much that they needed this land - it was actually originally just given to the tribe of Shimon on a temporary basis anyway - and so they forced them to leave. Verses 39-43 describe how some bands of Simeonites conquered areas outside of Eretz Yisrael and settled there, but evidently the bulk of the tribe went to live among the other tribes in the northern half of the Land; thus in II Chron. 15:9 and 34:6 they are associated with Menashe and Ephraim.
Also worth pointing out: in Bereishis Rabbah 98:10, R' Tanchuma says that "all of [the Cities of Refuge] were from the tribe of Shimon." Matnos Kehunah explains that the 24000 Simeonites who died during the affair of Baal Peor (Rashi to Num. 26:13) should indeed by rights have been given large territories in the Land of Israel; on their deaths their widows inherited these properties, so that each tribe absorbed about two thousand of them, and those areas were designated as the cities for the Levi'im. (Though Etz Yosef explains this Midrash differently.) According to this, too, most of the tribe lived outside the borders of Yehudah and Binyamin.