After doing some brief research, I found that it can be illegal in (at least) California - @DavePhD mentions in comments that similar laws also exist for North Dakota and Nebraska, and may exist for other states as well.
6980.54. (a) A locksmith licensed by the bureau shall be subject to
the provisions of Section 466.6 of the Penal Code, and shall be able
to duplicate any key for any vehicle from another key.
(b) A locksmith licensed by the bureau shall be subject to the
provisions of Section 466.8 of the Penal Code, and shall be able to
duplicate any key for a residence, commercial establishment, or
personal property from another key, except as follows:
(1) Duplication is prohibited when a key is stamped, imprinted,
marked, or incised with the wording "Do Not Duplicate" or "Unlawful
To Duplicate" and includes the originator's company name and
(2) Duplication is prohibited when a key is a Restricted Key or a
High Security Key and includes the originator's company name and
telephone number or registration number.
Generally, keys marked like this are for apartments or other commercial locks, so from @nomenagentis's answer,
the technician suspects wrongful intent
is a very likely suspicion when the key is marked in this way. While this is just speculation and I'm not sure how one would find out exactly, I would guess that Wal-mart (and many other locksmiths) just make this a company-wide policy to be safe.