Encontré la solución:
Hacer un replace antes de enviar:
Código HTML:
ajax.setRequestHeader('Content-Type','application/x-www-form-urlencoded');
valores = valores.replace('+','%2B');
ajax.send(valores);
El amigo abimaelrc en este foro ya respondió a una duda similar:
http://www.forosdelweb.com/f77/codificacion-datos-post-para-ajax-749170/#post3147492
Gracias!