I'm not sure about the Korean explanation, but it definitely predates the strategy game Starcraft, which was first released in 1998, and was at least five years earlier in beat-'em-up games such as Street Fighter II.
Searching Usenet, I found cheese strategy used on Aug 22, 1993 in alt.games.sf2 in a post called "SF2:HF(Turbo) Ken Strategy Guide".
<=-Zangief-=> He cheats a lot. You will get tough breaks every once in a
while in this fight, so bear (heh) with it. The cheese strategy is just to
use straight up and down Roundhouse kicks, or if you are in the corner, jump
back and use Roundhouse, then sweep/FB or DP when you land.
Here's the cheese strategy involves making simple, easy moves to defeat your opponent. These moves were often described as cheese moves or just cheese.
Another Street Fighter II thread of Dec 6, 1992 in rec.games.video.arcade titled "Cheese glorious Cheese!" includes cheese used a verb and a noun:
But Blanka is pretty much helpless if it is a really
good player who has decided to play this way. Cheese the livin' hell
out of them. And they're more than welcome to try to cheese back,
reason being that the above guy is right about the Blanka-Bison cheese.
A definition was given in alt.games.sf2 on Jun 18, 1992 in "Bison's Cheesepeedo":
"Cheese" is a term used to refer to anything cheap, unfair, or something
that is easy to do, does much damage, and requires no skill. For example,
some people consider the Ken fireball, fireball, dragon punch combo
to be cheese because it can be next to impossible to get out of it (by the
way, I do'nt think this combo is cheese). Of course, the magic throw and
freeze/handcuffs that two-bit Guile assholes use is BEYOND cheese.
The reason people called the torpedo the "Cheesepedo" (I myself call
it the pieceofsh*tpedo) is because it's a dead easy move to execute
(takes no skill at all...just yank back on stick and then forward,
hitting punch button) and does incredible damage, even when blocked.
A no-talent piece of trash playing Champion Edition could (and many
do) know nothing about the game and still beat you with the cheesepedo
by simply mowing across the screen, back and forth.
Capcom had no brain when they put this stupid, f**king move inthe
game. M.Bison "experts" are a bunch of asswipes with no talent.
Nuff said.
Cheese move dates back to at least Apr 6, 1992 in "SF2 TCE Match Ups" in rec.games.video.arcade:
Bison
jumping roundhouse, jab, fierce flame torpedo
neckkick, jab, sonic boom with roundhouse
VERY CHEESE MOVE: strong flame and throw
The very earliest mention I found of this cheese in any form (although I expect there will be earlier ones) was in "SFII (SFI)", posted to rec.games.video.arcade on Jan 27, 1992:
You couldn't choose your character; if you played
on the left, you were Ryu, and if you played on the right, you were Ken. Their
abilities were exactly matched, but not as extensive as in SFII... The two-player version was extremely fierce, though, because the game had absolutely no
cheese.
Finally, a July 1994 rec.games.video.arcade thread debates "To cheese or not to cheese" and an October 1993 alt.games.sf2 thread discusses the (regional) differences between ticking, cheesing, cheating and cheaping. Perhaps cheese comes from a combination of "cheap" (as in a cheap move), "cheat" and "easy".