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.