Arbitrary vs. Random
I originally wrote a more ambivalent response, but thinking about it further I've changed my mind.
It's clear that the phrase "let $x$ be a random integer" is mathematically . . . bad. What is at question is whether:
it is misleading to the student,
it is worth correcting,
and as a bonus, whether it is worth penalizing when repeated.
I think the answer to (3) is no (unless one is in a class dealing with probability), and the answer to (2) is yes, since if nothing else explaining why the phrase is wrong lets you preemptively address some of the usual confusions around quantifiers (e.g. we're allowed to pick a number that happens to be a counterexample "out of a hat").
I think the answer to (1) (and here's where I've changed my mind) is "yes" - or rather, it is "yes" enough that we should treat it as "yes." I think this is a case where poor use of language early on could set the student up for more confusion down the road, even if they are not being confused by the phrase at the moment. (And this is generally an argument for helping students with language use in mathematics.)
That said, I still think the answer to (3) is no (again, unless the class is dealing with probability).
In common parlance, random and arbitrary are often used interchangeably. A quick check of on-line dictionaries confirms that the semantic overlap is well established in spite of the different origins of the two words.
The fledgling proof-writers need to be made aware that this is not the case in math, with random being used when probabilities are involved. On the other hand, "Let $x$ be an arbitrary integer; then $P(x)$ holds" translates $\forall x \in \mathbb{Z} \,.\, P(x)$ into English.
Next, it would probably help the aforementioned fledglings if they were shown why the distinction is useful. One practical reason is simplicity. If one deals with an arbitrary integer $x$, all that is assumed is that $x \in \mathbb{Z}$. Could $x = 25$ be true? Of course! Could $x = 25$ be false? Certainly!
If, however, $x$ is a randomly chosen integer, not much may be said without knowing the distribution from which $x$ was drawn. The probability of $x = 25$ may be greater than $0$ if the distribution is not uniform (as it must be if the sample space is countable). Besides, as you may well know, zero probability doesn't mean impossible. By avoiding the use of random all these issues are sidestepped.
In more advanced courses, students will be able to appreciate more reasons for keeping random and arbitrary, as well as probabilistic and nondeterministic, distinct. But the example above should be enough to get them started. At any rate, in framing my feedback to students at their first attempts with proofs, I'd assume that they had the right concept in mind, but didn't pick the correct mathematical term to express it.
Actual dictionary definitions: Doing some quick dictionary searching for "arbitrary" gives the definition: "based on random choice or personal whim, rather than any reason or system." The definition given for "random" is "made, done, happening, or chosen without method or conscious decision." In fact, "random" is listed as a synonym for "arbitrary" on an online dictionary. Therefore the interchanging of the two terms is completely understandable.
Technical vs natural language: While it is true that "arbitrary" vs "random" have very different technical meanings in mathematics, they are nearly interchangeable in natural language. It is important to distinguish between natural and technical language usage/meaning.
I would explain this distinction between natural and technical language to my students. That is something that is students of any discipline should be aware of. There may be a risk of muddying the waters though since mastering the actual mathematics at hand may or may not be helped by this discussion of language.
Are you doing the "right" thing in correcting them? Offering a student relevant correct information is always the "right" thing to do. However, it may not always be the right thing to do if there is sufficient risk of it causing more confusion.
Language is a huge problem in mathematics. It's not something that is taught well in my opinion, in terms of how to actually speak mathematics. At least, if the way my students talk is any indication, there is generally a huge gap in being able to do mathematics and being able to explain it verbally in a coherent fashion using technical terminology correctly.
The physical process of choosing a number: Now let's consider the actual physical process of a human choosing an arbitrary number (in the technical sense here). It might be the case that such a physical process could be modeled using a random variable.
So, inasmuch as it is a real process of coming up with an actual example of an arbitrary number, it might actually be a type of random number in the probabilistic modeling sense. Of course, in the actual mathematical context where the number is to be used, it is just an arbitrary number, e.g. to be plugged into an equation.