Bueno, acá estamos de nuevo, después de tanto investigar e ir probando diferentes cosas se llegó a la solución. Ahora anda todo: acentos, espacios y los términos que poseen el carácter "+" (mas).
La cuestión es que deje tal cual tenía la función "encodeURIComponent()" en mi archivo JavaScript para tomar la parte que viene de la URL, o sea codificar.
Luego, lo que se agrego fue desde PHP una función que trabaja con un patrón de búsqueda con expresión regular.
Esta en la siguiente web para el que le pueda interesar:
http://mwop.net/blog/133-PHP-decoding-of-Javascript-encodeURIComponent-values.html Saludos!!!