Immagino che per la decodifica usi unescape().

Comunque l'errore e` nella funzione di codifica, che fa una sostituzione ibrida.

Per unescape ci vorrebbe &20 al posto dello spazio.

In alternativa, per correggere in JS:

str = str.replace(/\+/g, " ");

Ciao
Michele