He does not tell you to take it to Outworld. Hes says to take it the the Edenian palace.

Actually he does tell you to give the letter to a member of shao Kahns army.
Anyway you give the letter to a guard near the edenian palace(an edenian guard)to pretty much betray reiko. I forget the exact location, but hes near a small bridge, The location could be C5. The guard will give you some coins.

actually you can either give reiko's letter to an edenian guard or one of shao kahns soldiers. i have gone different routes both times i have played. you get koins either way. also its like tanyas mission you can either go talk to liu kang or find the cave and tell tanya. theres probably more missions just like these we just have to find out what other options there are. maybe if you do all the good ones or all the bad ones something different will happen. i remember reading that last statement somewhere on this site cant remember where though.