Bueno, al final, deduciendo y probando una hipótesis he llegado a la conclusión que tu error no está en el SP ni en la lógica de las tablas, sino en un elemento más simple:
Estás haciendo mal la llamada al SP.
El caso es que en vez de estár ingresando el parámetro como un string, estás poniendo el parámetro como el nombre de una variable.
Me explico:
Si yo llamo al SP así:
Mysql interpreta que quiero buscar la cadena "xxx" en el campo
Nombre_Cliente.
Pero si en cambio lo invoco así:
lo que intenta comparar es al campo
Nombre_Cliente con un campo llamado
XXX. Esto significa que está interpretando el nombre de un parámetro como nombre de un campo... que en realidad no existe. y entonces el problema pasa a ser de programación.
Tienes dos opciones:
1. Parametrizar la sentencia de llamada (fácil de hacer si trabajas en VB.Net o Java) para ingresar el valor de la variable por el nombre de la variable.
2. Construir la sentencia (PHP) de modo que el valor de la variable quede encerrado entre dos apóstrofes ('xxx').
Pruébalo y me cuentas.