El problema no es el tamaño del where, sino el orden y forma en que se estructuró los campos de la tabla.
Si yo se que voy a poner 2 nombres y 2 apellidos, lo más sano y razonable es crear 4 campos: nombre1, nombre2, apellido1, apellido2 y darles un máximo controlado por mi. Por ejemplo, es muy difícil que existan nombres y apellidos mayores a 20, entonces declaro mis campos nombres y apellidos de largo varchar(20). Luego, al realizar un SELECT, va a ser más fácil y eficiente obtener los resultados.
En tu caso, lo que podrías hacer es realizar es una búsqueda no completa ayudandote con un LIKE de esta forma:
Código PHP:
SELECT * FROM usuario WHERE apellido LIKE "mi cadena%"
De esa forma, te va a extraer todo lo que sea igual a "mi cadena" o que tenga al principio "mi cadena" y otros caracteres.