To be “in deep kimchi” is to be “in deep trouble” or “in deep doo-doo” or “in deep shit.”  Kimchi is a spicy a Korean delicacy consisting of pickled cabbage.
   
“In deep kimchi” was printed in The Christian Science Monitor (Boston, MA) on September 26, 1978. The early citations are clear that the term came from the military.
 
It is sometimes claimed that the expression comes from the Korean War (1950-1953), but there are no printed citations from that period. However, it is possible that the expression came from military personnel serving on bases in South Korea.
       
   
Wikipedia: Kimchi
Kimchi (/ˈkɪmtʃiː/; Korean: 김치, romanized: gimchi, IPA: [kim.tɕʰi]), a staple in Korean cuisine, is a traditional side dish of salted and fermented vegetables, such as napa cabbage and Korean radish, made with a widely varying selection of seasonings including gochugaru (chili powder), spring onions, garlic, ginger, and jeotgal (salted seafood), etc. It is also used in a variety of soups.
           
26 September 1978, The Christian Science Monitor (Boston, MA), “The Key General Nobody Knows” by Stephen Webbe, pg. B13, col. 2:
Others credit Gen. Jones with being “the principal and most vocal” supporter of the AWACS (Airborne Warning and Control System) radar plane program when it was “in deep kimchi” and with convincing Defense Secretary Harold Brown that it was wrong for the Air Force to kill its last wing of the F-15 fighters and replace it with two other wings of F-16 fighters or A10 ground attack aircraft.
       
Newspapers.com
22 October 1978, The Sunday News (Agana, Guam), “Commentary” by Stephen Webbe (Christian Science Monitor), Islander sec., pg. 14, col. 2:
Others credit Gen. Jones with being “the principal and most vocal” supporter of the AWACS (Airborne Warning and Control System) radar plane program when it was “in deep kimchi” and with convincing Defense Secretary Harold Brown that it was wrong for the Air Force to kill its last wing of the F-15 fighters and replace it with two other wings of F-16 fighters or A10 ground attack aircraft.
 
Newspapers.com
3 January 1980, Fort Worth (TX) Star-Telegram, “Afghan coup pressures US to find Mideast base sites” by George C. Wilson (Washington Post), pg. 2A, col. 2:
“We have an expression in the Pentagon,” said one general in stating that Afghanistan would provide a fresh sense of urgency for the bases, “that every time we get into deep kimchi (a Korean spicy cabbage dish) the Russian do us a favor.”
 
Google Books
How to Profit from the Money Revolution:
The Insider’s Guide to Financial Supermarkets, Their Super Products, and Super Brokers
By Wayne F. Nelson
New York, NY: McGraw-Hill
1983
Pg. 131:
If you pull out money before age fifty-nine-and-one-half you are in deep kimchi.
 
Google Books
Dirty Little Secrets:
Military Information You’re Not Supposed to Know
By James F. Dunnigan and Albert A. Nofi
New York, NY: Morrow
1990
Pg. 286:
Deep Kimchi
“Deep kimchi” means big trouble, from a Korean delicacy whose principal ingredient is very hot peppers.
 
Google Groups: alt.atheism
Fundy juries
.(JavaScript must be enabled to view this email address)
May 15, 1990, 1:05:57 PM
to
(...)
If Chris is wrong, he’s in DEEP kimchi!
 
Twitter
Kassidy M Kearey
@kassidy
I hope your hovercraft’s stereo doesn’t play Hotel California on repeat, or we’re in deep kimchi.
5:41 PM · Aug 15, 2007·Twitter Web Client
   
Oxford Reference
Brewer’s Dictionary of Modern Phrase & Fable (2 ed.)
Edited by John Ayto and Ian Crofton
Publisher: Chambers Harrap Publishers Print Publication Date: 2009 Published online: 2011 Current Online Version: 2011
In deep kimchi.
In US military slang, in serious trouble. The expression, a humorous bowdlerization of ‘in deep shit’, was born during the Korean War (kimchi is a Korean delicacy consisting of pickled cabbage).
 
Urban Dictionary
In Deep Kimchi
In deep trouble
In deep shit
Damn we’re in deep kimchi
by Dancing with Fire December 17, 2010
 
Urban Dictionary
Deep Kimchi
Kimchi is an extremely hot Korean fermented cabbage. It is something you do not want to find yourself in.
The deeper it is buried in the pottery in the ground while fermenting, the hotter it is.
To find one’s self in in deep Kimchi is to find one’s self in deep shit.
When John was caught peeping at the principal’s wife, he was in deep kimchi.
by The High Rhulain March 03, 2012