As you noted, there is a Halacha that one’s Rabbi may not be beyond the Techum. It is for this reason that the Mishnah (Eruvin 3:5) uses the example of a Rabbi coming to town in its discussion of conditional Eruvei Techumin.
Now, we hold that Techumin are d’Rabbanan (Sotah 30b). By this logic, then, if one is unsure if the Rabbi is in the Techum, we can apply Safek d’Rabbanan l’Kula and therefore you can assume that he is.
Now, let’s say that you call up your Rabbi, or Skype him, or send him an email. In these scenarios, it’s necessary that both you and your phone/computer are within the same Techum, and that your Rabbi and his phone/computer are within the same Techum.
Let’s say that both you and your Rabbi are outside of the Techum; in this instance, you must be within each other’s Daled Amos.
As for the source that it’s until the Techum? That would be Shemos 33:7:
> וּמֹשֶׁה֩ יִקַּ֨ח אֶת־הָאֹ֜הֶל וְנָֽטָה־ל֣וֹ ׀ מִח֣וּץ לַֽמַּחֲנֶ֗ה הַרְחֵק֙ מִן־הַֽמַּחֲנֶ֔ה וְקָ֥רָא ל֖וֹ אֹ֣הֶל מוֹעֵ֑ד וְהָיָה֙ כָּל־מְבַקֵּ֣שׁ יְהוָ֔ה יֵצֵא֙ אֶל־אֹ֣הֶל מוֹעֵ֔ד אֲשֶׁ֖ר מִח֥וּץ לַֽמַּחֲנֶֽה׃
And Moshe took his tent and pitched it outside the camp, a distance away from the camp, and he called it the Tent If Meeting. Anyone who sook out Hashem would go out to the Tent of Meeting outside the camp.
As Rashi there notes, Moshe’s tent was 2000 Amos outside the camp. Why is this important? Because if it was any further, it would be outside the Techum, and his rulings would be invalid. Note that based on this source, all of these halachos are true even during the week, not just on Shabbos.
I should note, though, that it’s not that his decisions aren’t binding, per se, so much as them not being considered rulings. Therefore, it’s only rulings issued outside the Techum which are invalid, not the ones previously or subsequently made inside the Techum. It’s a deficiency in the ruling, rather than the person issuing them - in Yeshivish, a chisaron in the cheftza, not the gavra.
Note that none of this is applicable when there are no competent Rabbis in your area. In that situation, you may receive a psak from outside your Techum, as the d’Oraisa of learning Torah overrides the d’Rabbanan of learning Purim Torah.
Edit: I neglected to mention the halachos of sending a shliach to ask the question for you. Since we hold shelucho shel adam kimoso, all of these halachos would apply equally to the shliach, rather than the one who sent him.