After toying around with this on and off for three days I have a solution - I'll post it in case anybody comes across this in the future.
You should be urlencoding your string from javascript - the problem is that encode() (javascript function) doesn't play by the same rules. Using php's urldecode, which does play by the rules, doesn't get escape() all the way. Use javascripts encodeURIComponent() function instead. It's less powerful than encode but it plays by the rules.
The big problem has been single quotes. Because I'm dealing with French text I absolutely need to be able to pass both single quotes and accented chars. And so, I replace single quotes separately:
// javacript code
// %27 is our single quote encoded
hello = encodeURIComponent(hello);
hello = hello.replace(new RegExp(/'/g),\"%27\"); // replaces all single quotes
Now, when you recieve the info you can use urldecode() with PHP properly.
I've tested this with Japanese as well and it worked just fine.