I say use Korea Posts recorded delivery system. It works pretty much the same way as Fedex et al do and it's great. I had to send my passport to the British Embassy in Seoul. Went into the post office late Wednesday afternoon, filled in all the paperwork, paid about 10 bucks I think and received a tracking number where I was able to follow online on their English website. And too my surprise and amazement the package was received in Hong Kong the next day, Thursday at 9 a.m!

Their website is here if you want to look into further details

http://www.koreapost.go.kr/eng/main/index.jsp

By the way I take no responsibility if anything bad happens to your stuff!