In my opinion, I don't think scriptures talks about the exact location of Mleccha Desha. Different people talks about it differently. Like in Kishkindha Kanda, Ramayana:
तत्र म्लेच्छान् पुलिन्दान् च शूरसेनान् तथैव च |
प्रस्थालान् भरतान् चैव कुरूम् च सह मद्रकैः || || ४-४३-११
कांबोज यवनान् चैव शकान् पत्तनानि च |
अन्वीक्ष्य दरदान् चैव हिमवन्तम् विचिन्वथ || ४-४३-१२
There in the north, the provinces of Mleccha-s, Pulinda-s, that way Shurashena - Prasthala - Bharata - Kuru - Madraka - Kaambhoja - Yavana shall be scrutinized along with the cities of Shaka and Darada, and then search in Himalayas. [4-43-11,12]
According to Adi Parva, Mahabharata, Mlechchas are the descendants of Yayati.
"The sons of Yadu are known by the name of the Yadavas: while those of Turvasu have come to be called the Yavanas. And the sons of Drahyu are the Bhojas, while those of Anu, the Mlechchhas. The progeny of Puru, however, are the Pauravas, amongst whom, O monarch, thou art born, in order to rule for a thousand years with thy passions under complete control.'"
According to Medhatithi's Manubhashya (Commentary on Manusmriti), Mlechchas are people those do not belong to any of the four Varna.
The Mlecchas are the people who are known as lying beyond the pale of the four castes,—not included even among the Pratiloma castes; such as the Medas, the Andhras, the Śabaras and the Pulindas.
Now, coming to the main question: What do Scriptures say about doing Puja/Yajnas in "Mleccha Deshas"?
According to Manusmriti 2.23, land of Mlechchas is not fit for sacrificial rites.
कृष्णसारस्तु चरति मृगो यत्र स्वभावतः ।
स ज्ञेयो यज्ञियो देशो म्लेच्छदेशस्त्वतः परः ॥ २३ ॥
kṛṣṇasārastu carati mṛgo yatra svabhāvataḥ |
sa jñeyo yajñiyo deśo mlecchadeśastvataḥ paraḥ || 23 ||
But the region where the spotted deer roams by nature is to be known as the ‘land fit for sacrificial acts’; beyond that is the ‘land of the Mlecchas.’ (23)