I have often heard Jews refer to Jesus as "Yoshke". Is the origin of that appellation based on halachic issues regarding mentioning names of foreign deities, or some other Jewish law or custom? When was its first recorded use?
Yoshke is simply a Yiddish diminutive nickname for Yehoshua (Joshua, for which a parallel English nickname would be Josh). Thus, it was simply a way for European Jews to make reference to Jesus in a manner that (a) conveyed the idea that Jesus was not viewed as important and (b) not likely to be picked up on by nearby Gentiles.
I doubt there is any record of the earliest use of the name, as it was, and still is, used almost exclusively in speech.
I believe the original term was Yoshke Pandre referring to the notion that Jesus was not fathered by Joseph, a Jew but rather a Roman centurion named Panthera. The intent is to be derogatory. There is a chapter on this in Peter Schäfer's Jesus in the Talmud