I did a split $uri "/" and urlencoded each part, then joined it back together.
It appears that MS WebFolders clients still connect handle the URLs even if they are urlencoded, so the best bet is going to be to take out the message keys and use the system locale for the folder URLs.
